Apparatus and method to incrementally update single static assignment (SSA) form

Patent 6064820 Issued on May 16, 2000. Estimated Expiration Date:

May 27, 2018. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Analysis and optimization of array variables in compiler for instruction level parallel processor
Patent #: 5293631
Issued on: 03/08/1994
Inventor: Rau, et al.

System and method for solving monotone information propagation problems
Patent #: 5327561
Issued on: 07/05/1994
Inventor: Choi, et al.

Method of producing object program based on interprocedural dataflow analysis of a source program
Patent #: 5396627
Issued on: 03/07/1995
Inventor: Iitsuka

System and method for optimizing computer code using a compact data flow representation
Patent #: 5448737
Issued on: 09/05/1995
Inventor: Burke, et al.

Method of compilation optimization using an N-dimensional template for relocated and replicated alignment of arrays in data-parallel programs for reduced data communication during execution
Patent #: 5475842
Issued on: 12/12/1995
Inventor: Gilbert, et al.

Method and apparatus for finding induction variables for use in compiling computer instructions
Patent #: 5584027
Issued on: 12/10/1996
Inventor: Smith

Industrial controller with optimized execution of relay ladder logic programs
Patent #: 5623401
Issued on: 04/22/1997
Inventor: Baxter

Method and apparatus for an improved optimizing compiler
Patent #: 5659754
Issued on: 08/19/1997
Inventor: Grove, et al.

Method of replacing lvalues by variables in programs containing nested aggregates in an optimizing compiler
Patent #: 5710927
Issued on: 01/20/1998
Inventor: Robison

System and method to efficiently represent aliases and indirect memory operations in static single assignment form during compilation Patent #: 5768596
Issued on: 06/16/1998
Inventor: Chow, et al.

Inventor

Subrahmanyam, Pratap

Application

No. 085299 filed on 05/27/1998

US Classes:

717/160, Including loop717/154, Including analysis of program717/159Code restructuring

Examiners

Primary: Hafiz, Tariq R.
Assistant: Chaki, Kakali

International Class

G06F 009/45

Abstract

A method and apparatus for incrementally updating SSA form after loop unrolling. The incremental SSA tool generates a non-ambiguous new name, in SSA form, for each original name defined in a loop and used outside of the loop after loop unrolling, by using the existing CFG structure for the software code that is created by the compiler. The incremental SSA tool renames the uses in the tails of the loop of a name defined within the loop into new clone names. The incremental SSA tool uses the new clone names created in the tails of the loop to rename other uses outside of the loop, of names that are defined within the loop, into new clone names. Also, the incremental SSA tool reconciles loop unrolled names that are used outside of the loop with the new clone names by creating new incarnation names.

Other References

Nianshu et al.,"Precise dependence tree for scalars within nested loops" IEEE, 1997, pp. 356-361
Ramalingam et al., "An incremental algorithm for maintaining the dominator tree of a reducible flowgraph", POPL '94, ACM 1994, pp. 287-296
Lavery et al., "Unrolling based optimizations for modulo scheduling"Proc. of MICRO-28, 1995, pp. 327-337
Liu et al., "Loop induction variable canonicalization in parallelizing compilers", Proc. of PACT '96, IEEE 1996, pp. 228-237
Johnson et al., "Dependence -based program analysis", ACM SIGPLAN, 1993, pp. 78-89
Knobe et al., "Array SSA form and its use in parallelization", POPL '98, ACM, 1998, pp. 107-120
McConnell et al., "Using Static single assignmenet form in a code optimizer", ACM 1992, pp. 152-160
Cytron et al., "Efficient accomadation of May-alias information in SSA form", ACM SIGPLAN PLDI '93, ACM 1993, pp. 36-45
Jong-Deok Choi, et al., "Incremental Computation Of Static Single Assingment Form", International Business Machines Corporation, Software Solutions Division, Document Number TR ADTI-1995-019 (also available as STL TR 03.638), Nov., 1995 (Original version: Nov., 1992), pp. 1-17
Ron Cytron, et al., "Efficiently Computing Static Single Assignment Form And The Control Dependence Graph", ACM Transactions On Programming Languages And Systems, vol. 13, No. 4, Oct., 1991, pp. 451-490
Tibor Gyimothy (Ed.), "Compiler Construction", 6th International Conference, CC'96, Linkoping, Sweden, Apr. 24-26, 1996 Proceedings, pp. 252-267. "Effective Representation Of Aliases And Indirect Memory Operations In SSA Form