DETAILED ACTION
This action is in response to the claims filed July 7, 2026. Claims 1-20 are pending. Claims 1, 19, and 20 are independent claims. Claims 1, 4, 5, 10, 19, and 20 have been amended.
The rejection of the claims under 35 U.S.C. 112(b) is withdrawn in view of Applicant’s amendments to the claims.
The rejection of the claims under 35 U.S.C. 101 is maintained in view of Applicant’s arguments and amendments to the claims.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Regarding claim 1, 19, and 20, the limitations “extracting a plurality of control flow split node features of a control flow split node in the IR graph of the source code of the program”, “processing the plurality of control flow split node features … to output a branch frequency value of a branch from the control flow split node”, “adding the branch frequency value to a profile for the program”, and “… generate optimized code” as drafted, are functions that, under their broadest reasonable interpretation, recite the abstract idea of a mental process. The limitation encompasses a human mind carrying out the function through observation, evaluation, judgement, and/or opinion, or even with the aid of pen and paper. Thus, these limitations recite and fall under the “Mental Processes” grouping of abstract ideas under Prong 1.
Under Prong 2, this judicial exception is not integrated into a practical application. The additional limitations “with a regression machine learning model”, “executing an optimizer on the program according to the profile…”, “a system comprising: memory; and at least one computer processor for executing computer readable program code to perform operations comprising:”, and “a non-transitory computer readable medium comprising computer readable program code for causing a computer system to perform operations comprising” are recited at a high level of generality such that they amount to no more than mere instructions to apply the exception using a generic computer, and/or mere computer components. See MPEP 2106.05(f). The limitation “obtaining an intermediate representation (IR) graph of source code of a program” does nothing more than add the insignificant extra solution activity of merely gathering and transmitting data to the judicial exception. See 2106.05(g). Accordingly, the additional elements do not integrate the judicial exception into a practical application and the claim is therefore directed to the judicial exception.
Under Step 2B, the claims do not recite additional elements which are sufficient to amount to significantly more. As discussed above with respect to integration of the abstract idea into a practical application, the limitations “with a regression machine learning model”, “executing an optimizer on the program according to the profile…”, “a system comprising: memory; and at least one computer processor for executing computer readable program code to perform operations comprising:”, and “a non-transitory computer readable medium comprising computer readable program code for causing a computer system to perform operations comprising” amount to no more than mere instructions, or generic computer/computer components to carry out the exception. Mere instructions to apply an exception cannot provide an inventive concept. See MPEP 2106.05(f). For the limitation “obtaining an intermediate representation (IR) graph of source code of a program”, the courts have identified mere data gathering and transmitting as well-understood, routine, and conventional activity. See MPEP 2106.05(d). Accordingly, the claims are not patent eligible under 35 U.S.C. 101.
Claim 2 does not recite additional mental steps. Under Prong 2, the limitation “executing the optimized code” is directed to the insignificant extra solution activity of insignificant application. See MPEP 2106.05(g). Under Step 2B, executing optimized code is a well-understood, routine, and conventional activity. The claim recites insignificant extra-solution activity which also does not amount to significantly more. The background of US 5613121 A (“Method and System of Generating Combined Storage References” states “It is known to perform optimizations on the object code produced by a compiler to achieve improved execution speeds of the optimized object code…”. The background of US 5655122A (“Optimizing Compiler with Static Prediction of Branch Probability, Branch Frequency and Function Frequency” states “The branch frequencies, derived from the branch probabilities, may then be a more direct bases for storing the object code in a given order to optimize program execution”. The Background of US 5875317 A (“Boosting Control Method and Processor Apparatus Having Boosting Control Portion”) states, “To satisfy such a requirement, a compiler that generates execution code for the processor analyzes the dependency of data for a corresponding software and changes the sequence of the operations according to the analyzed result, without changing the purpose of the software, so as to optimize the execution code”. These indicate that it is well-known, routine, and conventional to execute optimized code. Thus, executing optimized code does not amount to significantly more than the judicial exception and cannot provide an inventive concept.
Regarding claim 3, the limitation “changing the branch frequency value of a corresponding branch in the profile based on a heuristic rule” is an additional mental step. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 4, the limitation “based on the corresponding branch corresponding to a loop body, comparing the branch frequency value to a minimum threshold, wherein the branch frequency value is changed to a revised value responsive to the branch frequency value being less than the minimum threshold” is an additional mental step. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 5, the limitation “based on the corresponding branch corresponding to a program end, comparing the branch frequency value to a maximum threshold, wherein the branch frequency value is changed to the maximum threshold responsive to the branch frequency value being greater than the maximum threshold” is an additional mental step. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 6, the limitations “extracting a first set of features from the control flow split node”, “extracting a second set of features from a hosting block of a control flow graph, wherein the hosting block comprises the control flow split node, and wherein the control flow graph is generated from the IR graph”, and “combining the first set of features and the second set of features into the plurality of control flow split node features” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 7 the limitations “extracting a first set of features from the control flow split node”, “extracting a second set of features from a hosting block of a control flow graph, wherein the hosting block comprises the control flow split node, and wherein the control flow graph is generated from the IR graph”, “extracting a third set of features from at least one predecessor block of the hosting block”, and “combining the first set of features, the second set of features, and the third set of features into the plurality of control flow split node features” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 8, the limitations “extracting a first set of features from the control flow split node”, “extracting a second set of features from a hosting block of a control flow graph, wherein the hosting block comprises the control flow split node, and wherein the control flow graph is generated from the IR graph”, “extracting a third set of features from at least one successor block of the hosting block”, and “combining the first set of features, the second set of features, and the third set of features into the plurality of control flow split node features” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 9, the limitations “extracting a first set of features from the control flow split node”, “extracting a second set of features from a hosting block of a control flow graph, wherein the hosting block comprises the control flow split node, and wherein the control flow graph is generated from the IR graph”, “extracting a third set of features from at least one predecessor block of the hosting block”, “extracting a fourth set of features from at least one successor block of the hosting block”, and “combining the first set of features, the second set of features, the third set of features, and the fourth set of features into the plurality of control flow split node features” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 10, the limitation “concatenating the plurality of control flow split node features into a feature vector” is an additional mental step. The limitation “wherein processing the plurality of control flow split node features comprises processing the feature vector” is a mere instruction to apply “processing” to a feature vector, which does not amount to practical application under Prong 2, nor to significantly more under Step 2B. See MPEP 2106.05(f).
Regarding claim 11, the limitations “estimating, based on a set of nodes in a block of a control flow graph, an assembly size of the block, wherein the control flow graph is generated from the IR graph” and “adding the assembly size to the plurality of control flow split node features” are additional mental processes. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 12, the limitations “summing, across a set of nodes in a block of a control flow graph, an estimated number of processing cycles of each node in the set of nodes based on a node type of the node to generate an estimated number of processing cycles of the block, wherein the control flow graph is generated from the IR graph” and “adding the estimated number of processing cycles of the block to the plurality of control flow split node features” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 13, the limitations “totaling, across a set of nodes in a block of a control flow graph, a number of processing cheap nodes in the set of nodes based on a node type of each node in the set of nodes, wherein the number of processing cheap nodes are estimated to use less than a first threshold number of processing cycles, wherein the control flow graph is generated from the IR graph” and “adding the number of processing cheap nodes of the block to the plurality of control flow split node features” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 14, the limitations “totaling, across a set of nodes in a block of a control flow graph, a number of processing expensive nodes in the set of nodes based on a node type of each node in the set of nodes, wherein the number of processing expensive nodes are estimated to use more than a second threshold number of processing cycles, and wherein the control flow graph is generated from the IR graph” and “adding the number of processing expensive nodes of the block to the plurality of control flow split node features” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 15, the limitations “partitioning a plurality of nodes in a block of a control flow graph according to a node type of each node in the plurality of nodes to obtain a plurality of partitions, wherein the control flow graph is generated from the IR graph” and “generating a control flow split node feature of the plurality of control flow split node features based on a number of nodes in each partition of the plurality of partitions” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 16, the limitations “counting floating nodes in a set of nodes in a block of a control flow graph to obtain a count, wherein the control flow graph is generated from the IR graph” and “adding the count as a control flow split node feature of the plurality of control flow split node features” are additional mental steps. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Regarding claim 17, the limitations “generating a training IR graph of training source code of a training program”, “extracting a training plurality of control flow split node features of a training control flow split node in the training IR graph”, “processing,…, the training plurality of control flow split node features to generate a predicted branch frequency value of a second branch from the training control flow split node”, “adding the predicted branch frequency value to a predicted profile for the training program”, “instrumenting the training program to obtain an instrumented program”, “calculating a loss between the dynamic profile and the predicted profile”, and “updating the regression machine learning model according to the loss” are additional mental steps. The additional limitations “by the regression machine learning model”, and “executing the instrumented program to generate a dynamic profile of the instrumented program” merely applies a generic computer/computer components to the judicial exception, which does not amount to practical application under Prong 2, nor to significantly more under Step 2B, as explained above.
Regarding claim 18, the limitation “wherein calculating the loss comprises: calculating a difference between an execution frequency for the control flow split node obtained from dynamic profile and the predicted branch frequency value for the control flow split node” is an additional mental step. The claim does not recite additional elements which may integrate the judicial exception into a practical application under Prong 2, nor to significantly more under Step 2B.
Allowable Subject Matter
Claims 4-5 and 13-14 would be allowable if rewritten to overcome the rejection(s) under 35 U.S.C. 101, set forth in this Office action and to include all of the limitations of the base claim and any intervening claims.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-3, 6, 8, 10-12, 15, and 17-20 are rejected under 35 U.S.C. 103 as being unpatentable over “VESPA: Static Profiling for Binary Optimization” by Moreira et. al, (hereinafter “Moreira”), in view of “Dominance-based Duplication Simulation (DBDS): Code Duplication to Enable Compiler Optimizations” by Leopoldseder et. al, (hereinafter “Leopoldseder”), and further in view of “Static Branch Prediction for LLVM IRs Using Machine Learning” by Shih et. al (hereinafter “Shih”).
Regarding claim 1, Moreira discloses:
A method comprising:
…
- extracting a plurality of [branch] features of a [branch] in the [graph] (Page 3, “A program is formed by basic blocks, which are arranged in a control flow graph (CFG). A basic block is a sequence of non-branch instructions, except for the last one; thus, if we disregard preemption at the OS level, these instructions will be executed in sequence. The instructions in a basic block are naturally placed together in memory. A CFG is a directed graph where each vertex is a basic block. An edge between two blocks, e.g. BB𝑖 to BB𝑗, indicates that control may flow from BB𝑖 to BB𝑗. In this case, we say that BB𝑗 is a successor of BBi”; Page 6, “Example 3.1. Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function”; Page 7, “Example 3.3 (Static Program Feature). Consider the instruction “branch 𝑝0 ℓexit” in Figure 1(a). Several program features are associated with this instruction. A first feature is the opcode used to implement this instruction, e.g., in x86’s machine code: jne, je, jg, jle, jl, and jge. A second feature is the opcode used to produce the value 𝑝0. This opcode could be any arithmetic or logic operation. A third feature is the direction of the branch: forward or backward. In this example, we have a forward branch”) [Examiner’s remarks: An IR branch contain nodes with split off due to branch instructions. Features that are related to that branch (node in IR graph) are extracted.]…;
…
- adding the branch frequency value to a profile for the program (Page 2, “During prediction, we build a static profile for an unknown program. To this end, the model predicts the outcome of this program’s branches based on the features that characterize them”; Page 5, “A static profiler, like its dynamic counterpart, builds a map that associates control flow edges with their execution frequencies. The vast majority of static techniques depart from branch probabilities. In other words, they seek to estimate the chance that a conditional branch can be taken”) [Examiner’s remarks: Static profile for the program is build using branch frequency estimates from the model.]; and
- executing an optimizer on the program according to the profile to generate optimized code (Page 2, “During prediction, we build a static profile for an unknown program. To this end, the model predicts the outcome of this program’s branches based on the features that characterize them. These probabilities are then passed to a binary optimizer to guide its optimization decisions”) [Examiner’s remarks: The profile (static profile) of the code are used by the binary optimizer to optimize code.].
Moreira does not explicitly disclose:
- obtaining an intermediate representation (IR) graph of source code of a program;
- IR graph
- control flow split node
- … of the source code of the program;
- processing
However, Leopoldseder discloses:
- obtaining an intermediate representation (IR) graph of source code of a program (Pages 129, “Graal IR is a sea-of-nodes-based [9] directed graph in SSA form [10]. Each IR node produces at most one value. Data flow is represented with upward edges and control flow with downward edges. The IR is a superposition of the control-flow and the data-flow graph”);
- IR graph (Pages 129, “Graal IR is a sea-of-nodes-based [9] directed graph in SSA form [10]. Each IR node produces at most one value. Data flow is represented with upward edges and control flow with downward edges. The IR is a superposition of the control-flow and the data-flow graph”) [Examiner’s remarks: Moreira discloses having a control flow graph. Moreira does not disclose the graph being an IR graph. However, Leopoldseder discloses having the graph be derived from an intermediate representation, as is common in Graal IR. Therefore, one of ordinary skill in the art may replace the control flow graph of Moreira with the IR graph of Leopoldseder which also represents control-flow to achieve the present limitation.]
- control flow split node (Page 132, “Additionally, we use probability information at each control-flow split to determine relative basic block execution frequencies. The probability information is generated from HotSpot’s [26] profiling information”) [Examiner’s remarks: Moreira discloses having nodes which contain branches as the last instruction to form a control flow graph. Thus, each node splits due to the branch. Moreira further discloses deriving features from the branches and surrounding blocks. Moreira does not explicitly state using control flow split nodes. However, Leopoldseder explicitly states that control flow split nodes may be used for information collection.]
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Leopoldseder into the teachings of Moreira to include “obtaining an intermediate representation (IR) graph of source code of a program”, “IR graph”, and “control flow split node”. As stated in Leopoldseder, “We present a duplication optimization cost model that tries to maximize peak performance while minimizing code size and compilation time” (Page 127). Leopoldseder discloses using information to achieve program optimization statically. This optimization minimizes code while maximizing time saved. Usage of graphs allows for easy visualization of the flow of a program for analysis. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with control flow graphs.
The combination of Moreira and Leopoldseder does not explicitly disclose:
- … of the source code of the program;
- processing
However, Shih discloses:
- … of the source code of the program (Page 5, Figure 1, “Figure 1: ProGraML [15] representation for a sample IR. First the program is compiled to an LLVM intermediate representation. To construct the graph, each instruction, identifier, and value is added as a vertex the vertices are connected via control-flow, data-flow and call-flow edges.”) [Examiner’s remarks: The combination of Moreira and Leopoldseder discloses extracting features from a graph which may be a control flow graph containing control flow nodes. Shih explicitly discloses that the control flow graph may be generated from the intermediate representation of a source code program. One of ordinary skill in the art understands that the procedures of Moreira and Leopoldseder used on control flow graphs may be performed on the control flow graph generated from source code as disclosed by Shih.];
- processing(Page 5, Figure 1, “Figure 1: ProGraML [15] representation for a sample IR. First the program is compiled to an LLVM intermediate representation. To construct the graph, each instruction, identifier, and value is added as a vertex the vertices are connected via control-flow, data-flow and call-flow edges.”; Page 5, “We propose using a graph neural network (GNN) for predicting branch bias on a graph-based representation of LLVM IRs. We choose ProGraML [15] as our graph-based representation. ProGraML represents an IR as a directed graph where each instruction, identifier, and value is a vertex and each vertex is connected via control-flow, data-flow and call-flow edges. Figure 1 shows a ProGraML representation of an example program. To pass through our model, each vertex is embedded to learnable embedding with 32 dimensions using an augmented inst2vec [16] vocabulary. The entire graph is then passed through 8 generalized graph convolutional layers defined by Li et al. [17]. Each layer sequentially updates each vertex’s hidden feature representation by aggregating information from adjacent vertices. Then, for each vertex that corresponds to a branch instruction, we pass its final feature representation through a linear classifier that predicts the branch’s bias.”; Page 5, “We trained five classical machine learning models for branch prediction: decision tree, SVM, random forest, XGBoost, KNN. We used the scikit-learn python package to train these models. We choose hyper-parameters by conducting leave-one-out cross validation”) [Examiner’s remarks: Shih discloses using a regression machine learning model (e.g. XGBoost, GNN) on the IR-graphs of the source code along with feature information of the vertex (control flow split nodes) to predict a branch frequency (branch bias predicts how often a branch is executed). One of ordinary skill in the art understands that the graph and features extracted in Moreira and Leopoldseder may be used in the regression model taught by Shih to predict branch frequency.];
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Shih into the combined teachings of Moreira and Leopoldseder to include “of the source code of the program” and “processing
Regarding claim 2, the rejection of claim 1 is incorporated; and Moreira further discloses:
- executing the optimized code (Page 2, “Summary of Results. We have implemented our static profiler on top of the BOLT binary optimizer [Panchenko et al. 2019]. This new version of BOLT has been evaluated on four large executables: clang, GCC, MySQL and PostgreSQL. Experiments reported in Section 5 show that the binaries generated by BOLT fed with the static profiles inferred by VESPA are on average around 6% faster than the same program compiled with clang-O3”).
Regarding claim 3, the rejection of claim 1 is incorporated; and Moreira further discloses:
- changing the branch frequency value of a corresponding branch in the profile based on a heuristic rule (Page 15: “Classic Predictors. The other branch prediction heuristic that we have added to BOLT is the static profiler proposed by Wu and Larus [1994]. As mentioned in Section 1, Wu and Larus use Dempster Shafer Theory [Dempster 1967] to combine nine branch-characterization features proposed by Ball and Larus [1993]. Table 6 lists these features. This table also shows the probability that a branch with the given feature is taken. We have computed such probabilities over a training corpus yet to be described in Section 5. In that section, we shall refer to this heuristic as Wu-Larus”) [Examiner’s remarks: Heuristics are used to change the probabilities (frequencies) of a branch).].
Regarding claim 6, the rejection of claim 1 is incorporated; and Moreira further discloses:
- extracting a first set of features from the [branch] (Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 1, “OPCODE: the opcode of the branch instruction”) [Examiner’s remarks: Features for the branch (opcode of the branch) is extracted.];
- extracting a second set of features from a hosting block of a control flow graph, wherein the hosting block comprises the [branch], … (Page 3, “A program is formed by basic blocks, which are arranged in a control flow graph (CFG). A basic block is a sequence of non-branch instructions, except for the last one; thus, if we disregard preemption at the OS level, these instructions will be executed in sequence”; Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 6, “LOOP_HEADER: whether the basic block containing the branch is a loop header”) [Examiner’s remarks: Features from the hosting block (basic block) of the branch is extracted including whether the block has a loop header.]; and
- combining the first set of features and the second set of features into the plurality of [branch] features (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function”) [Examiner’s remarks: The features are combined into a vector for prediction.].
Moreira does not explicitly disclose:
- control flow split node
- … and wherein the control flow graph is generated from the IR graph; and
However, Leopoldseder discloses:
- control flow split node (Page 132, “Additionally, we use probability information at each control-flow split to determine relative basic block execution frequencies. The probability information is generated from HotSpot’s [26] profiling information”) [Examiner’s remarks: Leopoldseder discloses extracting profiling information from a control flow split node to determine frequencies. Control flow split nodes are equivalent to branches in the program. Therefore, gathering features at a branch as described by Moreira may be combined with the information gathering at control-flow splits of Leopoldseder.]
- … and wherein the control flow graph is generated from the IR graph (Pages 129, “Graal IR is a sea-of-nodes-based [9] directed graph in SSA form [10]. Each IR node produces at most one value. Data flow is represented with upward edges and control flow with downward edges. The IR is a superposition of the control-flow and the data-flow graph”); and
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Leopoldseder into the teachings of Moreira to include “control flow split node” and “and wherein the control flow graph is generated from the IR graph”. As stated in Leopoldseder, “We present a duplication optimization cost model that tries to maximize peak performance while minimizing code size and compilation time” (Page 127). Leopoldseder discloses using information to achieve program optimization statically. This optimization minimizes code while maximizing time saved. Usage of graphs allows for easy visualization of the flow of a program for analysis. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with control flow graphs.
Regarding claim 8, the rejection of claim 1 is incorporated; and Moreira further discloses:
- extracting a first set of features from the [branch] (Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 1, “OPCODE: the opcode of the branch instruction”) [Examiner’s remarks: Features for the branch (opcode of the branch) is extracted.];
- extracting a second set of features from a hosting block of a control flow graph, wherein the hosting block comprises the [branch], … (Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 6, “LOOP_HEADER: whether the basic block containing the branch is a loop header”);
- extracting a third set of features from at least one successor block of the hosting block (Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 12, “TS_LOOP_HEADER: whether the taken successor basic block is a loop header”) [Examiner’s remarks: A feature is extracted for the successor block of the hosting block, e.g., whether the successor block is a loop header.]; and
- combining the first set of features, the second set of features, and the third set of features into the plurality of [graph] features (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function”).
Moreira does not explicitly disclose:
- control flow split node
- … and wherein the control flow graph is generated from the IR graph; and
However, Leopoldseder discloses:
- control flow split node (Page 132, “Additionally, we use probability information at each control-flow split to determine relative basic block execution frequencies. The probability information is generated from HotSpot’s [26] profiling information”) [Examiner’s remarks: Leopoldseder discloses extracting profiling information from a control flow split node to determine frequencies. Control flow split nodes are equivalent to branches in the program. Therefore, gathering features at a branch as described by Moreira may be combined with the information gathering at control-flow splits of Leopoldseder.]
- … and wherein the control flow graph is generated from the IR graph (Pages 129, “Graal IR is a sea-of-nodes-based [9] directed graph in SSA form [10]. Each IR node produces at most one value. Data flow is represented with upward edges and control flow with downward edges. The IR is a superposition of the control-flow and the data-flow graph”); and
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Leopoldseder into the teachings of Moreira to include “control flow split node” and “and wherein the control flow graph is generated from the IR graph”. As stated in Leopoldseder, “We present a duplication optimization cost model that tries to maximize peak performance while minimizing code size and compilation time” (Page 127). Leopoldseder discloses using information to achieve program optimization statically. This optimization minimizes code while maximizing time saved. Usage of graphs allows for easy visualization of the flow of a program for analysis. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with control flow graphs.
Regarding claim 10, the rejection of claim 1 is incorporated; and Moreira further discloses:
- concatenating the plurality of control flow split node features into a feature vector (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function. The value that results from applying this function onto the feature vector is the probability that a branch is taken. Figure 4(d) shows a very simple linear predictor. The goal of the training phase is to build an accurate prediction function. The models that we explore in Section 3.5 are non-linear”) [Examiner’s remarks: The features for the branch (control flow split node) are concatenated into a vector for prediction.]; and
- wherein processing the plurality of control flow split node features comprises processing the feature vector (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other- -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function. The value that results from applying this function onto the feature vector is the probability that a branch is taken. Figure 4(d) shows a very simple linear predictor. The goal of the training phase is to build an accurate prediction function. The models that we explore in Section 3.5 are non-linear”).
Regarding claim 11, the rejection of claim 1 is incorporated; and Moreira further discloses:
- adding the [feature] to the plurality of control flow split node features (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function. The value that results from applying this function onto the feature vector is the probability that a branch is taken. Figure 4(d) shows a very simple linear predictor. The goal of the training phase is to build an accurate prediction function. The models that we explore in Section 3.5 are non-linear”).
Moreira does not explicitly disclose:
- estimating, based on a set of nodes in a block of a control flow graph, an assembly size of the block, wherein the control flow graph is generated from the IR graph; and
- assembly size
However, Leopoldseder discloses:
- estimating, based on a set of nodes in a block of a control flow graph, an assembly size of the block, wherein the control flow graph is generated from the IR graph (Page 130, “The performance estimator returns a numeric run time estimation (called cycles) as well as a code size estimation for each IR node. We compute which nodes are new or deleted and can therefore compute a cycles saved (CS) measurement which tells us if a given optimization might increase peak performance. We compute code size increase in a similar fashion. The performance estimator is based on a performance cost model for IR nodes. Each IR node is given a cycle and size estimation that allows us to compare two nodes (instructions) with each other (see Section 5.3 for details)”; Page 132, “We express the meta information as Java Annotations1 per node class with enumeration values for the estimated cycles and code size. The costs are designed to be platform agnostic. Listing 7 shows the AbstractNewObjectNodeclass with an annotation specifying the cycles and code size of this IR node. We implemented the node cost annotations for over 400 different nodes in the Graal compiler. Based on these annotations, we can compute the costs and benefits of (sub)graphs. Additionally, we use probability information at each control-flow split to determine relative basic block execution frequencies”); and
- assembly size (Page 132, “We express the meta information as Java Annotations1 per node class with enumeration values for the estimated cycles and code size. The costs are designed to be platform agnostic. Listing 7 shows the AbstractNewObjectNodeclass with an annotation specifying the cycles and code size of this IR node. We implemented the node cost annotations for over 400 different nodes in the Graal compiler. Based on these annotations, we can compute the costs and benefits of (sub)graphs. Additionally, we use probability information at each control-flow split to determine relative basic block execution frequencies”)[Examiner’s remarks: Assembly size may be treated as a gathered feature with numerical value and inserted into the machine learning training as is done with all other features.]
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Leopoldseder into the teachings of Moreira to include “estimating, based on a set of nodes in a block of a control flow graph, an assembly size of the block, wherein the control flow graph is generated from the IR graph” and “assembly size”. As stated in Leopoldseder, “We present a duplication optimization cost model that tries to maximize peak performance while minimizing code size and compilation time” (Page 127). Leopoldseder discloses using information to achieve program optimization statically. This optimization minimizes code while maximizing time saved. Usage of such parameters in training may further help to further the optimization. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with assembly size.
Regarding claim 12, the rejection of claim 1 is incorporated; and Moreira further disclose:
- adding the [feature] of the block to the plurality of control flow split node features (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function. The value that results from applying this function onto the feature vector is the probability that a branch is taken. Figure 4(d) shows a very simple linear predictor. The goal of the training phase is to build an accurate prediction function. The models that we explore in Section 3.5 are non-linear”).
Moreira does not explicitly disclose:
- summing, across a set of nodes in a block of a control flow graph, an estimated number of processing cycles of each node in the set of nodes based on a node type of the node to generate an estimated number of processing cycles of the block, wherein the control flow graph is generated from the IR graph; and
- estimated number of processing cycles
However, Leopoldseder discloses:
- summing, across a set of nodes in a block of a control flow graph, an estimated number of processing cycles of each node in the set of nodes based on a node type of the node to generate an estimated number of processing cycles of the block, wherein the control flow graph is generated from the IR graph (Page 130, “The performance estimator returns a numeric run time estimation (called cycles) as well as a code size estimation for each IR node. We compute which nodes are new or deleted and can therefore compute a cycles saved (CS) measurement which tells us if a given optimization might increase peak performance. We compute code size increase in a similar fashion. The performance estimator is based on a performance cost model for IR nodes. Each IR node is given a cycle and size estimation that allows us to compare two nodes (instructions) with each other (see Section 5.3 for details)”; Page 131, “Figure 3d shows the steps of the algorithm during the tra versal. We save value and type information for each involved IR node and update it regularly via the synonym mapping. Eventually, we iterate the division operation (x / φ) inbm2 and apply a strength reduction [1] AC on it. It returns true and we perform the action step. The action step returns a new instruction (x >> 1), which we save as a synonym for the division node. Our static performance estimator yields that the original division needs 32 cycles to execute while the shift only takes 1 cycle. Therefore, the cycles saved (CS) is computed as 32−1 = 31, i.e., we estimate that performing the duplication and subsequent optimizations reduces the run time of the program by 31 cycles”); and
- estimated number of processing cycles (Page 132, “We express the meta information as Java Annotations1 per node class with enumeration values for the estimated cycles and code size. The costs are designed to be platform agnostic. Listing 7 shows the AbstractNewObjectNodeclass with an annotation specifying the cycles and code size of this IR node. We implemented the node cost annotations for over 400 different nodes in the Graal compiler. Based on these annotations, we can compute the costs and benefits of (sub)graphs. Additionally, we use probability information at each control-flow split to determine relative basic block execution frequencies”)[Examiner’s remarks: Number of cycles may be treated as a gathered feature with numerical value and inserted into the machine learning training as is done with all other features.]
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Leopoldseder into the teachings of Moreira to include “summing, across a set of nodes in a block of a control flow graph, an estimated number of processing cycles of each node in the set of nodes based on a node type of the node to generate an estimated number of processing cycles of the block, wherein the control flow graph is generated from the IR graph” and “estimated number of processing cycles”. As stated in Leopoldseder, “We present a duplication optimization cost model that tries to maximize peak performance while minimizing code size and compilation time” (Page 127). Leopoldseder discloses using information to achieve program optimization statically. This optimization minimizes code while maximizing time saved. Usage of such parameters in training may further help to further the optimization. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with estimated processing cycles as a feature.
Regarding claim 15, the rejection of claim 1 is incorporated; and Moreira further discloses:
- partitioning a plurality of nodes in a block of a control flow graph according to a node type of each node in the plurality of nodes to obtain a plurality of partitions, wherein the control flow graph is generated from the IR graph (Page 3, “A program is formed by basic blocks, which are arranged in a control flow graph (CFG). A basic block is a sequence of non-branch instructions, except for the last one; thus, if we disregard preemption at the OS level, these instructions will be executed in sequence. The instructions in a basic block are naturally placed together in memory. A CFG is a directed graph where each vertex is a basic block”; Table 2, ID 22, “NUM_STORES: number of store instructions in the basic block containing the branch”; Table 2, ID 26, “BASIC BLOCK SIZE: number of instructions in the basic block containing the branch”; Table 2, ID 27, “NUM_BASIC_BLOCKS: number of basic blocks in the function containing the branch”; Page 8, “Tables 2, 3 and 4 show the new set of features that we use to extend Calder et al.’s work. The motivation for these inclusions is empirical, meaning that we have evaluated several different features, which were, in the end, not chosen to compose the final feature set.”) [Examiner’s remarks: the blocks are partitioned based on type, including for example, the type being a store.]; and
- generating a control flow split node feature of the plurality of control flow split node features based on a number of nodes in each partition of the plurality of partitions (Page 3, “A program is formed by basic blocks, which are arranged in a control flow graph (CFG). A basic block is a sequence of non-branch instructions, except for the last one; thus, if we disregard preemption at the OS level, these instructions will be executed in sequence. The instructions in a basic block are naturally placed together in memory. A CFG is a directed graph where each vertex is a basic block”; Table 2, ID 22, “NUM_STORES: number of store instructions in the basic block containing the branch”; Table 2, ID 26, “BASIC BLOCK SIZE: number of instructions in the basic block containing the branch”; Table 2, ID 27, “NUM_BASIC_BLOCKS: number of basic blocks in the function containing the branch”; Page 8, “Tables 2, 3 and 4 show the new set of features that we use to extend Calder et al.’s work. The motivation for these inclusions is empirical, meaning that we have evaluated several different features, which were, in the end, not chosen to compose the final feature set.”) [Examiner’s remarks: The feature may be, for example, a count of the type store].
Regarding claim 17, the rejection of claim 1 is incorporated; and Moreira further discloses:
- generating a training … of training source code of a training program (Page 16, “To train our model, we used the eleven programs in SPEC CINT2006 plus 226 programs from the LLVM test-suite, for which we collected execution profiles using instrumentation. We have used 80% of the branches from these programs to train the prediction model”);
- extracting a training plurality of control flow split node features of a training control flow split node in the training IR graph (Page 18, “Therefore, we trained two versions of the Decision Tree classifier proposed in the original paper: one using Calder et al.’s static features, and another using our extended set of program features. We then compared their branch prediction performance on the test set of programs. Since VESPA uses regression, we also trained two versions of a Decision Tree regressor with the same sets of features”) [Examiner’s remarks: A plurality of features is extracted during training form the branches.];
- processing, by the regression machine learning model, the training plurality of control flow split node features to generate a predicted branch frequency value of a second branch from the training control flow split node (Page 6, “The first, “Training”, consists in building the model that approximates the behavior of programs”; Page 19, “A metric typically used in the evaluation of regression models is the distance (error) between the observed and the predicted values. One such metric is the Root-Mean-Square Error (RMSE), which is the square root of the average of squared errors. The values used to compute this metric is the error measured in comparison with the probability of each branch being taken during dynamic execution. The lower is the error, the more accurate is the static predictor, as compared to a dynamic profiler. Table 7 summarizes the performance of these regressors. The regressor trained with VESPA’s feature set achieves lower prediction errors for all binaries in our evaluation set. This result shows that improvements due to our selection of features remain positive in decision trees.”) [Examiner’s Remarks: The model is run using the feature set to generate a predicted branch frequency (static prediction).];
- adding the predicted branch frequency value to a predicted profile for the training program (Page 19, “A metric typically used in the evaluation of regression models is the distance (error) between the observed and the predicted values. One such metric is the Root-Mean-Square Error (RMSE), which is the square root of the average of squared errors. The values used to compute this metric is the error measured in comparison with the probability of each branch being taken during dynamic execution. The lower is the error, the more accurate is the static predictor, as compared to a dynamic profiler. Table 7 summarizes the performance of these regressors. The regressor trained with VESPA’s feature set achieves lower prediction errors for all binaries in our evaluation set. This result shows that improvements due to our selection of features remain positive in decision trees.”) [Examiner’s remarks: A predicted branch frequency is added to the predicted profile (static predictor) to compare with the instrumented code during training.];
- instrumenting the training program to obtain an instrumented program (Page 16, “Benchmarks Used in the Development of the Model: To train our model, we used the eleven programs in SPEC CINT2006 plus 226 programs from the LLVM test-suite, for which we collected execution profiles using instrumentation”);
- executing the instrumented program to generate a dynamic profile of the instrumented program (Page 16, “Benchmarks Used in the Development of the Model: To train our model, we used the eleven programs in SPEC CINT2006 plus 226 programs from the LLVM test-suite, for which we collected execution profiles using instrumentation”; Page 19, “A metric typically used in the evaluation of regression models is the distance (error) between the observed and the predicted values. One such metric is the Root-Mean-Square Error (RMSE), which is the square root of the average of squared errors. The values used to compute this metric is the error measured in comparison with the probability of each branch being taken during dynamic execution. The lower is the error, the more accurate is the static predictor, as compared to a dynamic profiler”) [Examiner’s remarks: An instrumented program is run in order to collect dynamic profile data for comparison with the static predictor.];
- calculating a loss between the dynamic profile and the predicted profile (Page 19, “A metric typically used in the evaluation of regression models is the distance (error) between the observed and the predicted values. One such metric is the Root-Mean-Square Error (RMSE), which is the square root of the average of squared errors. The values used to compute this metric is the error measured in comparison with the probability of each branch being taken during dynamic execution. The lower is the error, the more accurate is the static predictor, as compared to a dynamic profiler”); and
- updating the regression machine learning model according to the loss (Page 19, “We trained two versions of a Decision-Tree based regressor: one using Calder et al.’s original features, and another using our proposed feature set. Their performances have been evaluated on the four binaries that we use for validation. A metric typically used in the evaluation of regression models is the distance (error) between the observed and the predicted values. One such metric is the Root-Mean-Square Error (RMSE), which is the square root of the average of squared errors. The values used to compute this metric is the error measured in comparison with the probability of each branch being taken during dynamic execution. The lower is the error, the more accurate is the static predictor, as compared to a dynamic profiler”).
Moreira does not explicitly disclose:
- IR graph
However, Leopoldseder discloses:
- IR graph (Pages 129, “Graal IR is a sea-of-nodes-based [9] directed graph in SSA form [10]. Each IR node produces at most one value. Data flow is represented with upward edges and control flow with downward edges. The IR is a superposition of the control-flow and the data-flow graph”)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Leopoldseder into the teachings of Moreira to include “IR graph”. As stated in Leopoldseder, “We present a duplication optimization cost model that tries to maximize peak performance while minimizing code size and compilation time” (Page 127). Leopoldseder discloses using information to achieve program optimization statically. This optimization minimizes code while maximizing time saved. Usage of graphs allows for easy visualization of the flow of a program for analysis. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with control flow graphs.
Regarding claim 18, the rejection of claim 17 is incorporated; and Moreira further discloses:
- calculating a difference between an execution frequency for the control flow split node obtained from dynamic profile and the predicted branch frequency value for the control flow split node (Page 19, “A metric typically used in the evaluation of regression models is the distance (error) between the observed and the predicted values. One such metric is the Root-Mean-Square Error (RMSE), which is the square root of the average of squared errors. The values used to compute this metric is the error measured in comparison with the probability of each branch being taken during dynamic execution. The lower is the error, the more accurate is the static predictor, as compared to a dynamic profiler”) [Examiner’s remarks: The loss is calculated between probability during dynamic execution (dynamic profile) and the predicted value using the static predictor.].
Claim 19 is a system claim corresponding to the method claim hereinabove (claim 1). Therefore, claim 19 is rejected for the same reasons as set forth in the rejection of claim 1.
Claim 20 is a non-transitory computer readable medium claim corresponding to the method claim hereinabove (claim 1). Therefore, claim 20 is rejected for the same reasons as set forth in the rejection of claim 1.
Claims 7 and 9 are rejected under 35 U.S.C. 103 as being unpatentable over “VESPA: Static Profiling for Binary Optimization” by Moreira et. al, (hereinafter “Moreira”), in view of “Dominance-based Duplication Simulation (DBDS): Code Duplication to Enable Compiler Optimizations” by Leopoldseder et. al, (hereinafter “Leopoldseder”), and further in view of “Static Branch Prediction for LLVM IRs Using Machine Learning” by Shih et. al (hereinafter “Shih”), and further in view of “Profile Guided Optimization Without Profiles: A Machine Learning Approach” by Rotem and Cummins (hereinafter “Rotem”).
Regarding claim 7, the rejection of claim 1 is incorporated; and Moreira further discloses:
- extracting a first set of features from the [branch] (Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 1, “OPCODE: the opcode of the branch instruction”);
- extracting a second set of features from a hosting block of a control flow graph, wherein the hosting block comprises the [branch], …(Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 6, “LOOP_HEADER: whether the basic block containing the branch is a loop header”);
…
- combining the first set of features, the second set of features, and the third set of features into the plurality of [branch] features (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function”).
Moreira does not explicitly disclose:
- control flow split node
- … and wherein the control flow graph is generated from the IR graph; and
However, Leopoldseder discloses:
- control flow split node (Page 132, “Additionally, we use probability information at each control-flow split to determine relative basic block execution frequencies. The probability information is generated from HotSpot’s [26] profiling information”) [Examiner’s remarks: Leopoldseder discloses extracting profiling information from a control flow split node to determine frequencies. Control flow split nodes are equivalent to branches in the program. Therefore, gathering features at a branch as described by Moreira may be combined with the information gathering at control-flow splits of Leopoldseder.]
- … and wherein the control flow graph is generated from the IR graph (Pages 129, “Graal IR is a sea-of-nodes-based [9] directed graph in SSA form [10]. Each IR node produces at most one value. Data flow is represented with upward edges and control flow with downward edges. The IR is a superposition of the control-flow and the data-flow graph”); and
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Leopoldseder into the teachings of Moreira to include “control flow split node” and “and wherein the control flow graph is generated from the IR graph”. As stated in Leopoldseder, “We present a duplication optimization cost model that tries to maximize peak performance while minimizing code size and compilation time” (Page 127). Leopoldseder discloses using information to achieve program optimization statically. This optimization minimizes code while maximizing time saved. Usage of graphs allows for easy visualization of the flow of a program for analysis. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with control flow graphs.
The combination of Moreira, Leopoldseder, and Shih does not explicitly disclose:
- extracting a third set of features from at least one predecessor block of the hosting block;
However, Rotem discloses:
- extracting a third set of features from at least one predecessor block of the hosting block (Page 2, “Just like LLVM’s BPI analysis we collects many features using C++ code. We ask questions such as, "how many instructions are in each one of the basic blocks that the branch points to", and "does the right destination block dominate the branch". We also collect information about the presence of certain instructions such as return and exception handling instructions. We also record information about the loop nest, information about the parent block and position within the function”); and
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Rotem into the combined teachings of Moreira, Leopoldseder, and Shih to include “extracting a third set of features from at least one predecessor block of the hosting block”. As stated in Rotem, “We develop a novel statistical approach for predicting branch probabilities from static program features without access to profile information” (Page 2). Rotem discloses predicting branch frequencies using static information without profiling. Use of information including predecessor block information allows for prediction of how code will flow at branches. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with predecessor block information as a feature.
Regarding claim 9, the rejection of claim 1 is incorporated; and Moreira further discloses:
- extracting a first set of features from the [branch] (Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 1, “OPCODE: the opcode of the branch instruction”);
- extracting a second set of features from a hosting block of a control flow graph, wherein the hosting block comprises the [branch], … (Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 6, “LOOP_HEADER: whether the basic block containing the branch is a loop header”);
…
- extracting a fourth set of features from at least one successor block of the hosting block (Page 7, “On The Choice of Program Features. The original work of Calder et al. defined 30 static program features. We could reuse 21 of them, which are listed in Table 1”; Table 1 contains feature with ID 12, “TS_LOOP_HEADER: whether the taken successor basic block is a loop header”); and
- combining the first set of features, the second set of features, the third set of features, and the fourth set of features into the plurality of [branch] features (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function”).
Moreira does not explicitly disclose:
- control flow split node
- … and wherein the control flow graph is generated from the IR graph; and
However, Leopoldseder discloses:
- control flow split node (Page 132, “Additionally, we use probability information at each control-flow split to determine relative basic block execution frequencies. The probability information is generated from HotSpot’s [26] profiling information”) [Examiner’s remarks: Leopoldseder discloses extracting profiling information from a control flow split node to determine frequencies. Control flow split nodes are equivalent to branches in the program. Therefore, gathering features at a branch as described by Moreira may be combined with the information gathering at control-flow splits of Leopoldseder.]
- … and wherein the control flow graph is generated from the IR graph (Pages 129, “Graal IR is a sea-of-nodes-based [9] directed graph in SSA form [10]. Each IR node produces at most one value. Data flow is represented with upward edges and control flow with downward edges. The IR is a superposition of the control-flow and the data-flow graph”); and
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Leopoldseder into the teachings of Moreira to include “control flow split node” and “and wherein the control flow graph is generated from the IR graph”. As stated in Leopoldseder, “We present a duplication optimization cost model that tries to maximize peak performance while minimizing code size and compilation time” (Page 127). Leopoldseder discloses using information to achieve program optimization statically. This optimization minimizes code while maximizing time saved. Usage of graphs allows for easy visualization of the flow of a program for analysis. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with control flow graphs.
The combination of Moreira, Leopoldseder, and Shih does not explicitly disclose:
- extracting a third set of features from at least one predecessor block of the hosting block; and
However, Rotem discloses:
- extracting a third set of features from at least one predecessor block of the hosting block (Page 2, “Just like LLVM’s BPI analysis we collects many features using C++ code. We ask questions such as, "how many instructions are in each one of the basic blocks that the branch points to", and "does the right destination block dominate the branch". We also collect information about the presence of certain instructions such as return and exception handling instructions. We also record information about the loop nest, information about the parent block and position within the function”); and
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Rotem into the combined teachings of Moreira, Leopoldseder, and Shih to include “extracting a third set of features from at least one predecessor block of the hosting block”. As stated in Rotem, “We develop a novel statistical approach for predicting branch probabilities from static program features without access to profile information” (Page 2). Rotem discloses predicting branch frequencies using static information without profiling. Use of information including predecessor block information allows for prediction of how code will flow at branches. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with predecessor block information as a feature.
Claim 16 is rejected under 35 U.S.C. 103 as being unpatentable over “VESPA: Static Profiling for Binary Optimization” by Moreira et. al, (hereinafter “Moreira”), in view of “Dominance-based Duplication Simulation (DBDS): Code Duplication to Enable Compiler Optimizations” by Leopoldseder et. al, (hereinafter “Leopoldseder”), and further in view of “Static Branch Prediction for LLVM IRs Using Machine Learning” by Shih et. al (hereinafter “Shih”), and further in view of “Compilation Forking: A Fast and Flexible Way of Generating Data for Compiler-Internal Machine Learning Tasks” by Mosaner et. al, (hereinafter “Mosaner”).
Regarding claim 16, the rejection of claim 1 is incorporated; and Moreira further discloses:
- adding the [feature] as a control flow split node feature of the plurality of control flow split node features (Page 6, “Figure 4 illustrates how prediction works for a given branch in the target program. Prediction starts with feature extraction. Features are mined from the target program syntax. In this example, we assume a set of four features (whose descriptions appear in Table 1). Three of them assume binary values; the other -CMP_OPCODE- ranges over a category of values. Once features are extracted, they are arranged into a feature vector, which Figure 4(c) shows. Said vector is passed to a “prediction” function. The value that results from applying this function onto the feature vector is the probability that a branch is taken. Figure 4(d) shows a very simple linear predictor. The goal of the training phase is to build an accurate prediction function. The models that we explore in Section 3.5 are non-linear”).
The combination of Moreira, Leopoldseder, and Shih does not explicitly disclose:
- counting floating nodes in a set of nodes in a block of a control flow graph to obtain a count, wherein the control flow graph is generated from the IR graph; and
- the count
However, Mosaner discloses:
- counting floating nodes in a set of nodes in a block of a control flow graph to obtain a count, wherein the control flow graph is generated from the IR graph (Page 1, “We implemented compilation forking in the GraalVM compiler in a programming-language-agnostic way. To assess the quality of the generated data, we trained several machine learning models to replace compiler heuristics for loop-related optimizations”; Page 10, “Nodes in the graph can either have a fixed position in the control flow (fixed nodes) or can be executed anywhere as long as data dependencies are met (floating nodes)”; Page 15, Table 1 under Category Nodes contains “#floatingNodes”); and
- the count (Page 1, “We implemented compilation forking in the GraalVM compiler in a programming-language-agnostic way. To assess the quality of the generated data, we trained several machine learning models to replace compiler heuristics for loop-related optimizations”; Page 10, “Nodes in the graph can either have a fixed position in the control flow (fixed nodes) or can be executed anywhere as long as data dependencies are met (floating nodes)”; Page 15, Table 1 under Category Nodes contains “#floatingNodes”) [Examiner’s remarks: A count may be treated as a gathered feature with numerical value and inserted into the machine learning training as is done with all other features.].
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Mosaner into the combined teachings of Moreira, Leopoldseder, and Shih to include “counting floating nodes in a set of nodes in a block of a control flow graph to obtain a count, wherein the control flow graph is generated from the IR graph” and “the count”. As stated in Mosaner, “The trained models perform equally well to the highly-tuned compiler heuristics when comparing the geometric means of benchmark suite performances” (Page 1). Mosaner discloses a model for profiling which uses number of floating nodes as a feature for prediction. Knowing the nodes which may be re-ordered in compilation can aid in optimization by helping with reordering. Therefore, it would be obvious to one of ordinary skill in the art to combine program optimization with floating nodes as a feature.
Response to Arguments
Applicant's arguments filed July 7, 2026 have been fully considered but they are not persuasive.
Regarding the rejection under 35 U.S.C. 101, Applicant argues:
1. Step 2A, Prong 1: The Claims Do Not Recite a Mental Process
The Action characterizes extracting control flow split node features from an IR graph, processing those features by a regression machine learning model, adding a branch frequency value to a profile, and generating optimized code as mental processes that can be performed by a human mind through observation, evaluation, judgment, and opinion, or with the aid of pen and paper. This characterization is incorrect.
Amended claim 1 requires extracting a plurality of control flow split node features from an IR graph of the source code of the program. An IR graph is a sea-of-nodes-based directed graph in static single assignment (SSA) form, as described in the specification. The IR graph is a superposition of a data-flow graph and a control flow graph, where IR nodes represent operations, data dependencies, and control-flow transitions. The human mind cannot practically traverse the IR graph of a real software program, identify control flow split nodes within the SSA-form graph, and extract a plurality of numerical and categorical features for each such node.
Amended claim 1 further requires processing those extracted features with a regression machine learning model to output a branch frequency value. The specification describes the regression machine learning model as including gradient-boosted ensemble models (XGBoost), neural networks, and regression decision trees. These architectures process dozens or hundreds of numerical input features through multiple layers of learned transformations. The human mind cannot practically apply a trained regression machine learning model of this complexity to a plurality of control flow split node features and output a branch frequency value. The August 2025 USPTO Memorandum on mental processes reminds examiners that the mental processes grouping must not be expanded to AJ limitations that cannot practically be performed in the human mind. Processing control flow split node features with a regression machine learning model to output a branch frequency value is not an operation that can practically be performed in the human mind, with or without pen and paper. Therefore, the rejection should be withdrawn.
[See Remarks – Pages 9-10]
Examiner’s Response:
Examiner respectfully disagrees. First, Applicant assets that the human mind “cannot practically traverse the IR graph of a real software program, identify control flow split nodes within the SSA-form graph, and extract a plurality of numerical and categorical features for each such node”. The specification states that the “IR graph is a superposition of two directed graphs: the data-flow graph and the control-flow graph” (See Paragraph [0029]). The specification does not specify that any given graph must be in SSA form. The data-flow graph and control-flow graphs represent the control and dataflow of operations in a program. The human mind is capable of observing a graph, identifying nodes with diverging control flow, and observing features of that node. Second, in regards the Applicant’s argument that the claims cite regression machine learning models that may not be practically performed in the human mind, the rejection under 35 U.S.C. 101 does not reject the use of the models as a mental process. Rather, it rejects processing a set of features and generating a branch frequency as mental. The human mind is capable of using a set of features (information) to generate a prediction of how often a branch is taken. Citing usage of a regression machine learning model merely applies a generic computer/computer component to the mental process of branch prediction. Therefore, the rejection under 35 U.S.C 101 is maintained.
In the remarks, Applicant argues:
2. Step 2A, Prong 2: The Claims Are Directed to a Practical Application
Even if the claims were found to recite an abstract idea, the amended claims integrate any such exception into a practical application because the claims do not merely analyze data or invoke machine learning as a result-oriented tool. Rather, the claims apply specifically extracted IR-graph features of a control flow split node to output a branch frequency value, add that branch frequency value to a profile for the program, and execute an optimizer according to that profile to generate optimized code. The claim therefore uses any alleged abstract idea in a concrete compiler- optimization workflow that changes how source code is profiled and optimized.
MPEP § 2106.04(d) explains that a claim integrates a judicial exception into a practical application when the claim as a whole applies, relies on, or uses the exception in a manner that imposes a meaningful limit on the exception, such as by improving the functioning of a computer or improving another technology or technical field. Consistent with that guidance, Ex Parte Desjardins, Appeal No. 2024-000567 (PTAB Sept. 26, 2025) (precedential), emphasizes that software-based and machine-learning-based claims should be evaluated under the technological- improvement framework of Enfish and related precedent, and that claims reflecting a disclosed improvement to computer functionality or another technical field can satisfy Step 2A, Prong 2.
Here, the specification identifies a technological problem in compiler optimization: profile- guided optimization depends on accurate profile information, but dynamic profiling can impose instrumentation and execution overhead, while conventional static approaches may provide less accurate profile information. The amended claims recite the particular technical mechanism that addresses that problem. Specifically, claim 1 requires obtaining an IR graph of source code, extracting control flow split node features from a control flow split node in that IR graph, processing those features with a regression machine learning model to output a branch frequency value, adding that value to a profile for the program, and executing an optimizer according to that profile to generate optimized code. These limitations are not incidental field-of-use restrictions; they are the asserted improvement itself.
The practical application is also reflected in the way the claimed branch frequency value is used. The regression machine learning model does not merely produce information for display, classification, or human review. The output branch frequency value is added to a profile that is then used by an optimizer to generate optimized code. Thus, the claimed output is consumed by a compiler component to alter the optimization of the program. This recited use meaningfully limits the claim to a technological process and ties the machine-learning output to a concrete improvement in compiler operation.
Accordingly, the amended claims are analogous to the types of software and machine- learning claims recognized as eligible when the claimed limitations reflect a disclosed technical improvement. The claims do not preempt branch prediction, profiling, or machine learning generally. Instead, they are limited to a particular IR-level static profiling technique that extracts features from control flow split nodes, generates branch frequency values using a regression machine learning model, and uses those values in a compiler optimizer to generate optimized code. For at least these reasons, the amended claims integrate any alleged judicial exception into a practical application, and the § 101 rejection should be withdrawn.
[See Remarks – Pages 10-11]
Examiner’s Response:
Examiner respectfully disagrees. First, the features, “extracting a plurality of control flow split node features of a control flow split node in the IR graph of the source code of the program”, “processing the plurality of control flow split node features…to output a branch frequency value of a branch from the control flow split node”, “adding the branch frequency value to a profile for the program”, and “generate optimized code” are considered under Prong 1 for being directed to the abstract idea of a mental process, and not considered under Prong 2 or Step 2B. The additional elements considered under the Prong 2 analysis are the “obtaining…”, “executing…” and “with a regression machine learning model” steps. As discussed in the rejection under 35 U.S.C. 101, the “obtaining… step amounts to mere data gathering and the “executing…” step amounts to mere application of a generic computer component. Applicant’s cited limitations are comprised on mental steps, which can not be used under Prong 2 to amount to practical application. The regression machine learning model is recited as a generic machine learning model, and therefore amounts to a generic computer component that is applied to the mental step of generating a branch frequency value from control flow split node features. Therefore, the rejection under 35 U.S.C. 101 is maintained.
In the Remarks, Applicant Argues:
2. Step 2B: The Claims Recite Significantly More
Even if the claims were found to recite an abstract idea not integrated into a practical application, the claims recite additional elements that amount to significantly more than any abstract idea.
The Action characterizes the "by a regression machine learning model" and generic computer components as mere instructions to apply the exception using a generic computer. This characterization does not account for the specific ordered combination of obtaining an IR graph from source code, extracting a plurality of control flow split node features of a control flow split node in the IR graph of the source code, processing those features with a regression machine learning model to output a branch frequency value, adding the branch frequency value to a profile, and executing an optimizer on the program according to the profile. This ordered combination produces a result that no single element achieves standing alone and that no prior system achieves, namely a compiler that uses machine learning based static profiling to generate more accurate profiles and more precise optimized code. This combination is not merely a generic application of machine learning.
The Action cites US 5,613,121 A, US 5,655,122 A, and US 5,875,317 A as evidence that executing optimized code is well-understood, routine, and conventional. These references address only the generic step of executing optimized code. None of the three references discloses the specific combination of extracting control flow split node features from an IR graph of source code, processing those features with a regression machine learning model to output a branch frequency value, and adding that value to a profile for use in optimization. A reference that does not disclose the specific combination cannot establish that combination as well-understood, routine, and conventional. The art cited in the Action further confirms that the specific claimed combination is not conventional. Moreira does not extract features from an IR graph of source code. Moreira extracts features from binary code. Leopoldseder does not use a regression machine learning model. Leopoldseder uses runtime profiling information from HotSpot. Neither reference, individually or in combination, discloses the specific combination of IR-level feature extraction with regression machine learning model processing to output branch frequency values. The absence of this combination from all references made of record is affirmative evidence that the combination is not well-understood, routine, or conventional. Therefore, the rejection should be withdrawn.
[See Remarks: Pages 11-12]
Examiner’s Remarks:
Examiner respectfully disagrees. First, the features, “extracting a plurality of control flow split node features of a control flow split node in the IR graph of the source code of the program”, “processing the plurality of control flow split node features…to output a branch frequency value of a branch from the control flow split node”, “adding the branch frequency value to a profile for the program”, and “generate optimized code” are considered under Prong 1 for being directed to the abstract idea of a mental process, and not considered under Prong 2 or Step 2B. The additional elements directed to “obtaining…” and “executing…” amount to mere data gathering and mere application of a generic computer component respectively, which can not amount to practical application nor to significantly more. See MPEP 2106.05(d) and 2106.05(f). Furthermore, recitation of “a regression machine learning model to output” merely cites a generic machine learning model which amount to a generic computer component, and the machine learning model is only applied to the “processing…” step, which is a mental step. Therefore, the recitation of a regression machine learning model amounts to no more than mere application of generic computer program to the judicial exception, which does not amount to practical application, nor does it amount to significantly more. See MPEP 2106.05(f). Second, in regard to the claim that the currently cited references do not teach the new limitations in full, the new elements are rejected under the new reference “Shih”, as discussed under the 35 U.S.C. 103 rejection. Therefore, the rejection of the claims under 35 U.S.C. 101 is proper and maintained.
In the remarks, Applicant argues:
Claim 1: Moreira Does Not Teach Extracting Features from an IR Graph of Source Code
Amended claim 1 recites, in part:
extracting a plurality of control flow split node features of a control flow split node in the IR graph of the source code of the program[.]
These features require that the feature extraction operates on the IR graph of the source code of the program. An IR graph is an intermediate representation generated from source code during compilation, not a binary representation of an already-compiled program.
The Action maps this limitation to Moreira pages 3, 6, and 7, which disclose extracting features from the branches and blocks of a program arranged in a control flow graph. However, Moreira operates on binary code, not on an IR graph of source code. In the Introduction of Moreira, the authors describe VESPA as a static profiler implemented on top of BOLT, where BOLT is described as a binary optimizer that operates on already-compiled binary executables. The features that Moreira extracts (opcodes of branch instructions, loop header indicators, taken-successor properties) are features of the binary-level control flow graph, extracted from binary code after compilation has already occurred. The binary-level control flow graph that Moreira analyzes is not an IR graph of the source code of the program, as required by amended claim 1. Moreira does not teach extracting control flow split node features from an IR graph of the source code of a program, as required by amended claim 1.
Leopoldseder discloses an IR graph (the Graal IR), but Leopoldseder does not extract features from control flow split nodes of that IR graph. Leopoldseder uses runtime profiling information from HotSpot at control-flow splits to determine relative basic block execution frequencies. Leopoldseder does not extract node features from the IR graph and process them through a model. The combination of Moreira and Leopoldseder therefore does not teach extracting control flow split node features from an IR graph of the source code of the program. Because neither Moreira nor Leopoldseder, alone or combined, teaches extracting control flow split node features from an IR graph of the source code of the program, the rejection is not supported by the cited art. Therefore, the rejection should be withdrawn.
Examiner’s response:
The new limitation is taught by a combination of Moreira, Leopoldseder, and Shih. Moreira discloses a control flow graph representing a program with branches, and extracting branch features from the branches. Leopoldseder discloses an IR graph which contains control flow split nodes which represent branches of execution in code. Shih discloses generating the IR graph from source or program code. In combination, Moreira, Leopoldseder, and Shih disclose generating an IR control flow graph from source code and extracting features from control flow split nodes (branches).
In the remarks, Applicant argues:
Claim 1: Moreira Does Not Teach a Regression Machine Learning Model That Outputs a Branch Frequency Value
Amended claim 1 recites, in part: processing the plurality of control flow split node features with a regression machine learning model to output a branch frequency value of a branch from the control flow split node[.]
These features require that the regression machine learning model outputs a branch frequency value.
The Action maps this limitation to Moreira page 25, where Moreira states that VESPA uses "a regression model powered by a neural network" to process branch features. However, the model of Moreira outputs branch probabilities, which are values between zero and one representing the likelihood that a branch is taken. Moreira expressly distinguishes probabilities from frequencies and dedicates a separate section (Section 3.6, "From Probabilities To Execution Frequencies," pages 13- 14) to converting the model output into frequencies. As Moreira teaches, the machine learning model outputs probabilities for each branch and BOLT (the binary optimizer) relies on execution counts to carry out its optimizations, requiring an extension to BOLT with the capability to convert the branch probabilities into execution frequencies (id.). The conversion from probability to frequency is a separate engineering step performed outside the model, not an output of the model. Amended claim 1 requires the regression machine learning model to output the branch frequency value directly. Because Moreira's model outputs a probability that must be converted to a frequency by a separate step external to the model, Moreira does not teach a regression machine learning model that outputs a branch frequency value, as required by amended claim 1. Therefore, the rejection should be withdrawn.
Examiner’s response:
The new limitation is taught by “Static Branch Prediction for LLVM IRs Using Machine Learning” by Shih et. al, which teaches a regression machine learning model that can predict branch bias, which is a measure of how frequently a branch is executed.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to VIVIAN WEIJIA DUAN whose telephone number is (703)756-5442. The examiner can normally be reached Monday-Friday 8:30AM-5PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Wei Y Mui can be reached at (571) 272-3708. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/V.W.D./Examiner, Art Unit 2191 /WEI Y MUI/Supervisory Patent Examiner, Art Unit 2191
Prosecution Insights