[<<][rtl][>>][..]
Sun May 12 15:13:03 EDT 2019

Identifying reuse patterns

This needs a simplified notation.

Basically, map the full target language representation on something
simpler, definte operations on the simpler form to play with them and
find some operations, and then lift them to the target language
representation.

To make these transformations work, they need to be expressed in an
algebra.

Starting from where we were:

T c[100];
T d[100];
for(int i=0; i< 100); i++){
	c[i] = op(a[i], b[i])
	d[i] = op(c[i], c[i])
}


This can be stripped to

(def c 100)
(def d 100)
(loop i 100
  ((c i) (op (a i) (b i)))
  ((d i) (op (c i) (c i))))

Removing the definitions

(loop i 100
  ((c i) (op (a i) (b i)))
  ((d i) (op (c i) (c i))))


Ignoring the loop ranges: we know there is some range, but its extent
is non-essential.

(loop i
  ((c i) (op (a i) (b i)))
  ((d i) (op (c i) (c i))))

The tansformation is then between the above and

(loop i
  (c (op (a i) (b i)))
  ((d i) (op c c)))

The general rule: a dimension can be removed if a variable does not
escape a context.  ( Or if only the last variable does )

Then loop order for multiply-nested loops could be determined by
checking each order, and comparing the optimizations.



Removing mention of "op"

(loop i
  ((c i) (a i) (b i))
  ((d i) (c i) (c i)))

The tansformation is then between the above and

(loop i
  (c (a i) (b i))
  ((d i) (c c)))


Getting rid of parenthesis, where <- means binding + some abstracted
primitive operation.


i:
  c(i) <- a(i) b(i)
  d(i) <- c(i) c(i)

i:
  c()  <- a(i) b(i)
  d(i) <- c()  c()
  

Then get rid of operations and use upper case for array names, and lower case for indices

i:
   Ci <- Ai Bi
   Di <- Ci Ci

i:
   C  <- Ai Bi
   Di <- C  C 




[Reply][About]
[<<][rtl][>>][..]