Browse Prior Art Database

# An Algorithm of Variable Folding for Sequential Synthesis

IP.com Disclosure Number: IPCOM000120705D
Original Publication Date: 1991-May-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 1 page(s) / 50K

IBM

Wu, SM: AUTHOR

## Abstract

Variable unfolding is a technique to rename variables in a logic description such that no variable is assigned value more than once in any path of the resulting control flow graph. This paper presents a new algorithm which introduces pure value transfer operations to resolve the multiple definition problem of variables in a general control flow graph. We show that introducing pure value transfer operation is inexpensive or even free because the new variable can always use the same resource as the old one in that, after unfolded, the old variable must be dead (no longer referenced by others); it is also easy to handle since no status signal need be traced.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 70% of the total text.

An Algorithm of Variable Folding for Sequential Synthesis

Variable unfolding is a technique to rename variables in a
logic description such that no variable is assigned value more than
once in any path of the resulting control flow graph.  This paper
presents a new algorithm which introduces pure value transfer
operations to resolve the multiple definition problem of variables in
a general control flow graph.  We show that introducing pure value
transfer operation is inexpensive or even free because the new
variable can always use the same resource as the old one in that,
after unfolded, the old variable must be dead (no longer referenced
by others); it is also easy to handle since no status signal need be
traced.

Suppose variable x is defined at point p in a given control
flow graph.  We want to replace the x at p and all of its references
with a new variable t.  By depth first search, every descendant of p
is recursively visited until encountering a join vertex or a vertex
where x is redefined; during the search, all the visited references
of x are replaced with t.  As visiting a vertex whose successor is a
join vertex and where x is still live, this vertex is put into a set
Jlst.  Jlst is hence the set of vertices which are in the tree rooted
at p and whose successors are the first join vertices in the paths
starting from p; nevertheless, in the path between p and any element
in Jlst, x is not redefined and all the references of x have been
cha...