🚀 go-pugleaf

lka@lems17lems.brown.edu (Lalit K. Agarwal) writes:
>Has anyone played with converting CONTROL-DEPENDENCE to
>DATA-DEPENDENCE in High-Level-Synthesis or come across any algorithm
>for doing it in the literature.?  All suggestions are highly welcome.

I'm not sure what you mean by "high-level synthesis."
In vectorizing compilers, lots of people use "if conversion".
A paper is

  title="Conversion of Control Dependence to Data Dependence",
  author="J. R. Allen and Ken Kennedy and Carrie Porterfield and Joe Warren",
  pages="177--189",
  booktitle=popl10,
  year=1983,
  month=jan

where popl10 is proceedings of the Principles of Programming Languages
conference.

Preston Briggs

In article <1993Jan23.003531.21573@cs.brown.edu> lka@lems17lems.brown.edu (Lalit K. Agarwal) writes:
>Has anyone played with converting CONTROL-DEPENDENCE to DATA-DEPENDENCE in
>High-Level-Synthesis or come across any algorithm for doing it in the literature.?
>All suggestions are highly welcome.

This is common in APL and J. Both languages are array-oriented:
    1 2 3 + 8 4 2
9 6 5

so all primitives are defined on entire arrays, rather than on scalars.
Given this, programs are shorter, cleaner, more elegant, and more likely to
work if you describe algorithms in terms of array operations instead of loops.
Thus, you'll see expressions like this:

    X + 55* (X<4)     NB. Add 55 to those elements of X which are less than 4.

This involves knowledge of simple arithmetic identities, but there are
merge and selection capabilities which permit fancier stuff:
    t =. "this is my   text string'
    b =. t=' '
    b
0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0  
    NB. The above locates blanks in t.
    NB. Now replaces blanks by '*'.
    t[b/i. #b] =. '*'   NB. This is part APL, part J... 
    NB. #b is the shape of b, i.e., 24 
    NB. i. #b is the first #b integers.
    NB. b/i.#b removes from the list of #b integers those which are
        not corresponding to blanks.
    NB. t[...] =. '*' replaces the non-blank elements.   

This stuff is common in APL. Go read ACM SIGAPL Quote Quad conference 
proceedings for more examples, or come to APL93 in Toronto this August
15-19!
{I'm the Tutorials Chair...}

One last example: A model of a loom is 2.5 pages of BASIC (SEE P. Heiser,
August 1981 or so BYTE article {from memory}). This compresses into
about 12 characters of APL: Two indexing operations and one inner product.
It also runs bags faster than BASIC. Even on one processor... 8^}

Bob


Robert Bernecky      rbe@yrloc.ipsa.reuter.com  bernecky@itrchq.itrc.on.ca 
Snake Island Research Inc  (416) 368-6944   FAX: (416) 360-4694 
18 Fifth Street, Ward's Island
Toronto, Ontario M5J 2B9 
Canada