Apparatus and method to incrementally update single static assig

Details Apparatus and method to incrementally update single static assig Apparatus and method to incrementally update single static assig

1998-05-27

2000-05-16

Hafiz, Tariq R.

395707, 395708, G06F 945

Patent

active

060648201

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.

REFERENCES:
patent: 5293631 (1994-03-01), Rau et al.
patent: 5327561 (1994-07-01), Choi et al.
patent: 5396627 (1995-03-01), Iitsuka
patent: 5448737 (1995-09-01), Burke et al.
patent: 5475842 (1995-12-01), Gilbert et al.
patent: 5584027 (1996-12-01), Smith
patent: 5623401 (1997-04-01), Baxter
patent: 5659754 (1997-08-01), Grove et al.
patent: 5710927 (1998-01-01), Robison
patent: 5768596 (1998-06-01), Chow et al.
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".

Affiliated with

Also associated with

Rating

Apparatus and method to incrementally update single static assig does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus and method to incrementally update single static assig, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method to incrementally update single static assig will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-266539