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 .
DETAILED ACTION
This action is in response to the application filed on 09/12/2024.
Claims 1-3, 7-10 and 14-17 are pending.
Examiner’s Note
Please note that Examiner cites particular columns and line numbers in the references as applied to the claims below for the convenience of the applicant. Although the specified citations are representative of the teachings in the art and are applied to the specific limitations within the individual claim, other passages and figures may apply as well. It is respectfully requested that, in preparing responses, the applicant fully consider the references in entirely as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior art or disclosed by the examiner.
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.
Claim(s) 1-3, 7-10 and 14-17 is/are rejected under 35 U.S.C. 103 as being unpatentable over USPN 6128775 to Chow et al. in view of USPN 5448737.
Per Claim 1:
Chow discloses:
1. A method comprising:
constructing a static single assignment (SSA) form (Col. 8, line 53-55 “developed… a sparse SSA representation forms”) and a static single use (SSU) form for a program (Col. 8, line 64 “static single use (SSU) form is defined”);
setting a single-use disqualifying property locally for each SSU version (Col. 15, line 19-23 “local variables are dead (i.e., disqualify) at exits… they are assigned unique SSU versions”), and propagating the single-use disqualifying property both forward and backward on an SSU graph uniquely formed from the constructed SSU form (Col. 15, line 29-35 “forward propagation along the edges of the SSU graph… backward control flow path leading to the procedure entry”) so it becomes a global property (Col. 17, line 48-49 “stores are global variables, which tend to exhibit few store redundancies”) ;
transferring results from the SSU form to the SSA form to set a single-use property locally for each SSA version based on an occurrence of any use being associated with a disqualifying SSU version (Col. 12, line 49-62 “perform sparse computation of global data flow attributes based on the SSA graph for h… saved and computations that are redundant, and determines the use-def relationship among SSA versions… transforms the code to form the optimized output”);
performing data flow analysis on an SSA graph uniquely formed from the constructed SSA form (Col. 6, line 36-40 “data flow analysis on the sparse SSA representation”) so the single-use property becomes a global property to identify one or more definitions as dynamic single-use for variables in the program (Col. 13, line 41-50 “a static single use (SSU) form to be the dual of SSA form. In SSU form each use of a variable establishes a new version… a definition of the corresponding variable and always defines a new version, the SSU factoring operator A is regarded as a use of its variable and always establishes (uses) a new version”).
Chow does not explicitly disclose generating computer-readable instructions for executing the program based on the one or more definitions identified as dynamic single use for the variables in the program, wherein the one or more definitions identified as dynamic single-use has a defined value used exactly one time during execution of the program.
However, Burke discloses in an analogous computer system generating computer-readable instructions for executing the program (Col. 4, line 57-60 “transform a source program into optimized executable code or more generally from a source program to an optimized form”) based on the one or more definitions identified as dynamic single use for the variables in the program (Col. 9,10 line 59-60,19-22 “loop of this algorithm is performed once for each variable V in the program… every definition site in the program and the AllUse table has information for every use in the program”), wherein the one or more definitions identified as dynamic single-use has a defined value used exactly one time during execution of the program (Col. 17, line 57-67 “Each definition site d that defines variable v has an entry in AllDef table… determining the set of definitions that reach a given definition whose index value in the AllDef table… Each use site of variable v in this data structure is reached by at most one definition site of v. Likewise, each definition site in SSA form is reached by at most one definition”).
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention was made to incorporate the method of generating computer-readable instructions for executing the program based on the one or more definitions identified as dynamic single use for the variables in the program, wherein the one or more definitions identified as dynamic single-use has a defined value used exactly one time during execution of the program as taught by Burke into the method of optimizing compiler as taught by Chow. The modification would be obvious because of one of ordinary skill in the art would be motivated to add/incorporate the features of generating computer-readable instructions for executing the program based on the one or more definitions identified as dynamic single use for the variables in the program, wherein the one or more definitions identified as dynamic single-use has a defined value used exactly one time during execution of the program to provide an efficient technique generating computer program to which includes only needed definitions according the variables used and thus efficiently handle certain types of definitions so as to parallelizing compilers as suggested by Burke (col. 3, lines 5-12).
Per Claim 2:
Chow discloses:
2. The method of claim 1, wherein constructing the SSA form includes inserting function ϕ’s at dominance frontiers of definitions and uses and renaming variable definitions (Col. 9, line 39-43 “PRE generator 102 alters the previously-disclosed SSAPRE algorithm by modifying the Φ-Insertion and Rename steps (steps 1 and 2) to produce a new form such as SSU”; Col. 11, line 22-24 “Φ-Insertion step will also insert Φ's at the iterated dominance frontiers of left occurrences”) and uses by assigning SSA versions through a pre-order traversal of a dominator tree formed from a control flow graph (CFG) (Col. 12, line 2-8 “occurrence of C in the region of the control flow graph dominated by C__1 is fully redundant with respect to C__1”).
Per Claim 3:
Chow discloses:
3. The method of claim 1, wherein the SSU form is constructed on top of the SSA form, and wherein constructing the SSU form includes inserting function λ’s at post-dominance frontiers of definitions (Col. 14 line 53-57 “λ's have to be placed at the iterated post-dominance frontiers of each Store in the program. Second, λ’s also have to be placed when a killed Store reaches a Split point. Because Stores are killed by loads, λ’s have to be placed at the iterated post-dominance frontiers of each load (including aliased load) of the memory location”) and uses and renaming variable definitions and uses by assigning SSU versions through a pre-order traversal of a post-dominator tree formed from a control flow graph (CFG) (Col. 15, line 1-5 “Each λ is assigned a new SSU version because each λ is regarded as a use. The result of renaming is Such that any control flow path that includes two different versions must cross an (aliased) use of the memory location or a λ”).
Per Claim 7:
Chow discloses:
7. The method of claim 1, wherein the method is performed iteratively for the variables in the program and identifies whether each of the definitions in the program is dynamic single-use (Col. 2, line 41-45 “a static single assignment (SSA) representation of a computer program during compilation… program and it does not require any form of iterative data flow analysis”).
Claims 8-10 and 14 is/are the apparatus/system claims corresponding to method claims 1-3 and 7 respectively and rejected under the same rational set forth in connection with the rejection of claims 1-3 and 7 respectively, as noted above.
Claims 15-17 is/are the apparatus/system claims corresponding to method claims 1-3 respectively and rejected under the same rational set forth in connection with the rejection of claims 1-3 respectively, as noted above.
Allowable Subject Matter
Claims 4-6, 11-13 and 18-20 objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Related cited arts:
Tavares, A., et al. "SSI revisited: A Program Representation for Sparse Data-flow Analyses." Preprint submitted to Science of Computer Programming (2012). pp. 1-41.
Plevyak, John, and Andrew A. Chien. "Iterative flow analysis." Submitted, July (1995). pp.1-22.
Lin, Jin, et al. "Recovery code generation for general speculative optimizations." ACM Transactions on Architecture and Code Optimization (TACO) 3.1 (2006): pp. 67-89.
Cytron, Ron, et al. "An efficient method of computing static single assignment form." Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 1989. pp. 25-35.
US6292938 - An optimizing, compiler that performs retargetable object code generation for a specific processor by matching tree patterns in directed acyclic graphs derived from the source code.
US5768596 - A system and method for an optimizer of a compilation suite for representing aliases and indirect memory operations in static single assignment (SSA) during compilation of a program having one or more basic blocks of source code. The optimizer converts all scalar variables of said program to SSA form, wherein said SSA form includes a plurality of variable versions, zero or more occurrences of a .chi. function, zero or more occurences of a .phi. function, and zero or more occurrences of a .mu. function. The .chi. function, .phi. function, and .mu. function are inserted for the variable versions. The optimizer also determines whether a variable version can be renamed to a zero version, and upon such a determination, the optimizer renames the variable version to a zero version. The optimizer further converts all indirect variables of a program to SSA form, wherein the SSA form includes a plurality of virtual variable versions such that a virtual variable is assigned to an indirect variable, zero or more occurrences of a .chi. function, zero or more occurences of a .phi. function, and zero or more occurrences of a .mu. function. The .chi. function, .phi. function, and .mu. function are inserted for the virtual variables. The optimizer hashes a unique value number and creates a corresponding hash table entry for each variable version and each virtual variable remaining after renaming all zero versions. The optimizer also applies global value numbering to each basic block of the program.
US6026241 - Partial redundancy elimination of a computer program is described that operates using a static single assignment (SSA) representation of a computer program. The SSA representation of the computer program is processed to eliminate partially redundant expressions in the computer program. This processing involves inserting .PHI. functions for expressions where different values of the expressions reach common points in the computer program. A result of each of the .PHI. functions is stored in a hypothetical variable h. The processing also involves a renaming step where SSA versions are assigned to hypothetical variables h in the computer program, a down safety step of determining whether each .PHI. function in the computer program is down safe, and a will be available step of determining whether each expression in the computer program will be available at each .PHI. function following eventual insertion of code into the computer program for purposes of partial redundancy elimination. The processing also includes a finalize step of transforming the SSA representation of the computer program having hypothetical variables h to a SSA graph that includes some insertion information reflecting eventual insertions of code into the computer program for purposes of partial redundancy elimination, and a code motion step of updating the SSA graph based on the insertion information to introduce real temporary variables t for the hypothetical variables h.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Satish Rampuria whose telephone number is 571-272-3732. The examiner can normally be reached on Monday-Friday from 8:30 AM to 5:00 PM.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Chat Do, can be reached at telephone number 571-272-3721. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
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) Form at https://www.uspto.gov/patents/uspto-automated- interview-request-air-form.
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.
/Satish Rampuria/Primary Examiner, Art Unit 2193
*****
Prosecution Insights