Home My Page Projects Code Snippets Project Openings diderot

# SCM Repository

[diderot] View of /branches/vis15/src/compiler/high-opt/eps-util.sml
 [diderot] / branches / vis15 / src / compiler / high-opt / eps-util.sml

# View of /branches/vis15/src/compiler/high-opt/eps-util.sml

Thu Jul 28 14:38:10 2016 UTC (3 years, 2 months ago) by jhr
File size: 7365 byte(s)
`working on merge`
```(* eps-util.sml
*
* This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
*
* COPYRIGHT (c) 2015 The University of Chicago
*)

(* Helper functions for normalize-ein_exp
* does the rewriting for Epsilon and deltas
*)
structure EpsUtil : sig

val epsToDels : Ein.ein_exp list
-> (Ein.ein_exp * Ein.sumrange list) option * Ein.ein_exp list option * Ein.ein_exp list

val reduceDelta : Ein.ein_exp list * Ein.ein_exp list * Ein.ein_exp list
-> bool * Ein.ein_exp

val matchEps : Ein.mu list * Ein.mu list -> bool

end = struct

structure E = Ein

fun err str = raise Fail (String.concat["Ill-formed EIN Operator",str])

(* check to see if a pair of Epsilon expressions can be converted to deltas *)
fun doubleEps (E.Epsilon(a,b,c), E.Epsilon(d,e,f)) = let
fun createDeltas (s, t, u, v) =
(* FIXME: what does the following comment mean? *)
(*If multiple summation ids are the same, it might not remove from the summation queue*)
if (s=u andalso t=v) orelse (s=v andalso t=u)
then NONE
else let
val d1 = [E.Delta(s, u), E.Delta(t, v)]
val d2 = [E.Delta(s, v), E.Delta(t, u)]
in
SOME(d1, d2)
end
in
if (a=d) then createDeltas(b, c, e, f)
else if (a=e) then createDeltas(b, c, f, d)
else if (a=f) then createDeltas(b, c, d, e)
else if (b=d) then createDeltas(c, a, e, f)
else if (b=e) then createDeltas(c, a, f, d)
else if (b=f) then createDeltas(c, a, d, e)
else if (c=d) then createDeltas(a, b, e, f)
else if (c=e) then createDeltas(a, b, f, d)
else if (c=f) then createDeltas(a, b, d, e)
else NONE
end
| doubleEps _ = raise Fail "None Epsilon Argument"

(* distributeEps (epsAll, sumexp)
* ???
*)
(*distributeEps:ein_exp list* ein_exp list
-> int*ein_exp list * ein_exp list *ein_exp list *sum_index_id list
* ein_exp list
*epsAll is a list of epsilons
*sumExp is a summation expression with epsilon
* Before this function, there is call to filter all the epislons
* in a product expression.
*Sometimes a matching epislon can be hidden in a SummationExp, so that makes the search a little more complicated
*The arguments to this function are either
*(1) a list of epsilons in epsAll
*(2) or a single item in both epsAll and sumExp.
*In case (1), We check two epislons at a time for a match
*If there is match then we return unused epsilon list, and rewriten deltas pairs
*In case (2) We check the embedded eps for a match and if we find one return sum_ids and the rest of the product
*)
fun distributeEps (epsAll, sumexp) = let
fun distEps ([], _) = NONE
| distEps ([e1], eps) = (case sumexp
of [E.Sum(sx, E.Opn(E.Prod, e2::ps))] => (case doubleEps(e1, e2)
of SOME(d1, d2) =>  SOME(eps, d1, d2, sx, ps)
| NONE =>  NONE
(* end case *))
| _ => NONE
(* end case *))
| distEps (e1::e2::current,eps) = (case doubleEps(e1, e2)
of SOME(d1, d2) => SOME(eps@current, d1, d2, [], sumexp)
| _ => distEps(e2::current, eps@[e1])
(* end case *))
in
distEps (epsAll, [])
end

(*epsToDels:ein_exp list
-> int*ein_exp * sum_index_id*ein_exp list *ein_exp list
*Looks at ein_exp list and searches for epsilons
*calls above function to look for transition
*return: change, e', sx
*)
fun epsToDels exps = let
val (epsAll, rest, sumexp) = EinFilter.filterEps exps
(* DEBUG *
fun pp e = String.concatWith"," (List.map EinPP.expToString e)
val _ =print(String.concat["\n\nepsall:",pp epsAll,"\nresl:",pp rest, "\nsumexp",pp sumexp])
*)
in
case distributeEps(epsAll, sumexp)
of NONE => if (length epsAll > 0)
then (NONE, SOME epsAll, rest@sumexp)
else (NONE, NONE, rest@sumexp)
| SOME(epsUnused, d1, d2, sx, ps) => let
(* d1, d2 are rewritten delta expressions *)
(* in some cases there are embedded expressions of the form E.Sum(sx, ...ps)*)
(* sx does not apply to the rest of the expression ("rest")*)
(* return expression in pieces in order to preserve structure*)
val a = E.Opn(E.Prod, epsUnused@d1@ps)
val b = E.Opn(E.Prod, epsUnused@d2@ps)
in
(SOME(E.Op2(E.Sub, a, b), sx), NONE, rest)
end
(*end case *)
end

(* reduceDelta:ein_exp*ein_exp* ein_exp list ->int *ein_exp
* Apply deltas to tensors/fields
* returns change or rewriten ein_exp
*
* distPart:mu list*mu*mu* mu list
* looks for match with index_id and delta
* current delta is Delta_{i,j},Differentiation has index_ids pd
*
*  distribute:int*ein_exp list*ein_exp list *ein_exp list*ein_exp list
*  distribute deltas of ein_exp list
*)
fun reduceDelta (eps, dels, es)=let
fun appDel (changed, [], beta, mu, nu) = (changed, List.rev beta, mu @ List.rev nu)
| appDel (changed, a::alpha, beta, [], nu) = appDel(changed, alpha, a::beta, List.rev nu, [])
| appDel (changed, a::alpha, beta, E.Delta(i, j)::mu, nu) =
if (a = j)
then appDel(true, alpha, i::beta, mu, nu)
else appDel(changed, a::alpha, beta, mu, E.Delta(i, j)::nu)
(* FIXME: instead of appending singletons, build results in reverse order! *)
fun distribute (changed, [], rest, mu) = (changed, E.Opn(E.Prod, eps@mu@rest))
| distribute (changed, p1::ps, rest, mu) = (case p1
of E.Tensor(id, alpha) => let
val (changed, alpha_betas, nu) = appDel(changed, alpha, [], mu, [])
in
distribute(changed, ps, rest@[E.Tensor(id, alpha_betas)], nu)
end
| E.Field(id, alpha) => let
val (changed, alpha_betas, nu) = appDel(changed, alpha, [], mu, [])
in
distribute(changed, ps, rest@[E.Field(id, alpha_betas)], nu)
end
| E.Conv(v, alpha, h, dx) => let
val (changed, alpha_betas, nu1) = appDel(changed, alpha, [] ,mu, [])
val (changed, dx_betas, nu2) = appDel(changed, dx, [], nu1, [])
in
distribute(changed, ps, rest@[E.Conv(v,alpha_betas, h ,dx_betas)], nu2)
end
| E.Probe(E.Conv(v, alpha, h, dx), t) => let
val (changed, alpha_betas, nu1) = appDel(changed, alpha, [], mu, [])
val (changed, dx_betas, nu2) = appDel(changed, dx, [], nu1, [])
in
distribute(
changed, ps, rest@[E.Probe(E.Conv(v,alpha_betas, h ,dx_betas),t)], nu2)
end
| E.Apply(E.Partial d, e) => let
val (changed, d_betas, nu) = appDel(changed,d,[],mu,[])
in
distribute(changed, ps, rest@[E.Apply(E.Partial d_betas,e)],nu)
end
| _ => distribute(changed, ps, rest@[p1], mu)
(* end case *))
in
distribute (false, es, [], dels)
end

(* matchEps: checks if two different indices in 'ids' both appear in 'mus' *)
fun matchEps (ids, mus) = let
(* fun inMus id = List.exists (fn (E.C _) => false | (E.V x) => (x = id)) mus*)
fun inMus id = List.exists (fn x => (x = id)) mus
fun match0 [] = false
| match0 (id::ids) = if inMus id
then match1 (ids, id)
else match0 ids
and match1 ([], id) = false
| match1 (id::ids, id') = ((id <> id') andalso inMus id) orelse match1 (ids, id')
in
match0 ids
end

end
```