## Chapter 7. Data-flow Transformation (*)

### Work in Progress

This chapter is work in progress. Not all parts have been finished yet. The latest revision of this manual may contain more material. Refer to the online version.

This chapter shows examples of data-flow transformations

## 7.1. Preliminaries

Figure 7.1. file: til/opt/til-opt-lib.str

```module til-opt-lib
imports liblib TIL til-eval
strategies

contains(|x) =  // should be in stratego-lib
oncetd(?x)

elem-of(|xs) = // should be in stratego-lib
?x; where(<fetch(?x)> xs)

get-var-names =
collect(?Var(<id>))

get-var-dependencies =
collect(?Var(<!(<id>,<id>)>))

EvalExp =
EvalAdd <+ EvalMul <+ EvalSub <+ EvalDiv <+ EvalMod
<+ EvalLt <+ EvalGt <+ EvalEqu <+ EvalNeq

is-var =
?Var(_)

is-value =
?Int(_) <+ ?String(_)

is-pure-exp =
?Var(_) <+ ?Int(_) <+ ?String(_)
<+ is-bin-op#([is-pure-exp, is-pure-exp])

is-bin-op =
?"Or" <+ ?"And" <+ ?"Neq" <+ ?"Equ" <+ ?"Gt" <+ ?"Lt" <+ ?"Sub"
<+ ?"Add" <+ ?"Mod" <+ ?"Div" <+ ?"Mul"
```

## 7.2. Constant Propagation

Figure 7.2. file: til/xmpl/propconst-test2

```sglri -p ../syn/TIL.tbl -i propconst-test2.til |\
../sim/til-simplify |\
../opt/til-propconst |\
ast2text -p ../pp/TIL-pretty.pp -o propconst-test2.txt
```

Table 7.1. files: til/xmpl/propconst-test2.til, til/xmpl/propconst-test2.txt

beforeafter
```var x;
var y;
var z;
var a;
var b;
x := 1;        // constant value
y := 2;        // not constant
x := 3;        // override
a := x + 4;    // compute constant
y := x + z;    // not constant
if y then
z := 8;
x := z - 5;  // constant
else
x := a - 4;  // constant
z := a + z;  // z is not constant
end
b := a + z;    // a still constant, z not
z := a + x;
writeint(b + z);
```
```var x : int;
var y : int;
var z : int;
var a : int;
var b : int;
x := 1;
y := 2;
x := 3;
a := 7;
y := 3 + z;
if y then
z := 8;
x := 3;
else
x := 3;
z := 7 + z;
end
b := 7 + z;
z := 10;
write(int2string(b + 10));
```

Figure 7.3. file: til/opt/til-propconst.str

```module til-propconst
imports til-opt-lib
strategies

io-til-propconst =
io-wrap(propconst)

propconst =
PropConst
<+ propconst-declaration
<+ propconst-assign
<+ propconst-block
<+ propconst-if
<+ propconst-while
<+ all(propconst); try(EvalExp)

propconst-block =
Block({| PropConst : map(propconst) |})

propconst-declaration =
(?Declaration(x) <+ ?DeclarationTyped(x, t))
; rules( PropConst+x :- Var(x) )

propconst-assign =
Assign(?x, propconst => e)
; if <is-value> e then
rules( PropConst.x : Var(x) -> e )
else
rules( PropConst.x :- Var(x) )
end

propconst-if =
IfElse(propconst, id, id)
; (EvalIf; propconst
<+ IfElse(id, propconst, id) /PropConst\ IfElse(id,id,propconst))

propconst-while =
?While(_, _)
; (/PropConst\* While(propconst, propconst))
```

## 7.3. Copy Propagation

Figure 7.4. file: til/xmpl/copyprop-test2

```sglri -p ../syn/TIL.tbl -i copyprop-test2.til |\
../sim/til-simplify |\
../opt/til-copyprop |\
ast2text -p ../pp/TIL-pretty.pp -o copyprop-test2.txt
```

Table 7.2. files: til/xmpl/copyprop-test2.til, til/xmpl/copyprop-test2.txt

beforeafter
```var x : int;
var y : int;
y := x;
y := y + 1;
x := y;
write(int2string(x));
```
```var x : int;
var y : int;
y := x;
y := x + 1;
x := y;
write(int2string(y));
```

Figure 7.5. file: til/opt/til-copyprop.str

```module til-copyprop
imports til-opt-lib
strategies

io-til-copyprop =
io-wrap(copyprop)

copyprop =
CopyProp
<+ copyprop-declaration
<+ copyprop-assign
<+ copyprop-block
<+ copyprop-if
<+ copyprop-while
<+ all(copyprop)

copyprop-block =
Block({| CopyProp : map(copyprop) |})

copyprop-declaration =
(?Declaration(x) <+ ?DeclarationTyped(x, t))
; new-CopyProp(|x, x)

copyprop-assign =
Assign(?x, copyprop => e)
; undefine-CopyProp(|x)
; where( innermost-scope-CopyProp => z )
; if <?Var(y)> e then
rules( CopyProp.z : Var(x) -> Var(y) depends on [(x,x),(y,y)] )
end

copyprop-if =
IfElse(copyprop, id, id)
; (IfElse(id, copyprop, id) /CopyProp\ IfElse(id,id,copyprop))

copyprop-while =
?While(_, _)
; (/CopyProp\* While(copyprop, copyprop))

innermost-scope-CopyProp =
get-var-names => vars
; innermost-scope-CopyProp(elem-of(|vars))
```

## 7.4. Reverse Copy Propagation

Figure 7.6. file: til/opt/til-copyprop-rev.str

```module til-copyprop-rev
imports til-opt-lib
strategies

io-til-copyprop-rev =
io-wrap(copyprop-rev)

copyprop-rev =
CopyPropRev
<+ copyprop-rev-declaration
<+ copyprop-rev-assign
<+ copyprop-rev-block
<+ copyprop-rev-if
<+ copyprop-rev-while
<+ all(copyprop-rev)

copyprop-rev-block =
Block({| CopyPropRev : map(copyprop-rev) |})

copyprop-rev-declaration =
(?Declaration(x) <+ ?DeclarationTyped(x, t))
; new-CopyPropRev(|x, x)

copyprop-rev-assign =
Assign(?x, copyprop-rev => e)
; undefine-CopyPropRev(|x)
; where( innermost-scope-CopyPropRev => z )
; if <?Var(y)> e then
rules( CopyPropRev.z : Var(y) -> Var(x) depends on [(x,x),(y,y)] )
end

copyprop-rev-if =
IfElse(copyprop-rev, id, id)
; (IfElse(id, copyprop-rev, id) /CopyPropRev\ IfElse(id,id,copyprop-rev))

copyprop-rev-while =
?While(_, _)
; (/CopyPropRev\* While(copyprop-rev, copyprop-rev))

innermost-scope-CopyPropRev =
get-var-names => vars
; innermost-scope-CopyPropRev(elem-of(|vars))
```

## 7.5. Common-subexpression Elimination

Figure 7.7. file: til/xmpl/cse-test2

```sglri -p ../syn/TIL.tbl -i cse-test2.til |\
../sim/til-simplify |\
../opt/til-cse |\
ast2text -p ../pp/TIL-pretty.pp -o cse-test2.txt
```

Table 7.3. files: til/xmpl/cse-test2.til, til/xmpl/cse-test2.txt

beforeafter
```var a;
var b;
var x;
x := a + b;
writeint(a + b);
a := 23;
x := a + b;
writeint(a + b);
```
```var a : int;
var b : int;
var x : int;
x := a + b;
write(int2string(x));
a := 23;
x := a + b;
write(int2string(x));
```

Figure 7.8. file: til/opt/til-cse.str

```module til-cse
imports til-opt-lib
strategies

io-til-cse =
io-wrap(cse)

cse =
CSE
<+ cse-declaration
<+ cse-assign
<+ cse-if
<+ cse-block
<+ cse-while
<+ all(cse)

cse-block =
Block({| CSE : map(cse) |})

cse-declaration =
(?Declaration(x) <+ ?DeclarationTyped(x, t))
; new-CSE(|x, x)

cse-assign =
Assign(?x, cse => e)
; undefine-CSE(|x)
; if <not(contains(|Var(x)))> e then
where( innermost-scope-CSE => z )
; where( get-var-dependencies => deps )
; rules( CSE.z : e -> Var(x) depends on deps )
end

cse-if =
IfElse(cse, id, id)
; (IfElse(id, cse, id) /CSE\ IfElse(id,id,cse))

cse-while =
?While(_, _)
; (/CSE\* While(cse, cse))

innermost-scope-CSE =
get-var-names => vars
; innermost-scope-CSE(elem-of(|vars))
```

## 7.6. Forward Substitution

Figure 7.9. file: til/opt/til-forward-subst.str

```module til-forward-subst
imports til-opt-lib
strategies

io-til-forward-subst =
io-wrap(forward-subst)

forward-subst =
ForwardSubst
<+ forward-subst-declaration
<+ forward-subst-assign
<+ forward-subst-if
<+ forward-subst-block
<+ forward-subst-while
<+ all(forward-subst)

forward-subst-block =
Block({| ForwardSubst : map(forward-subst) |})

forward-subst-declaration =
(?Declaration(x) <+ ?DeclarationTyped(x, t))
; new-ForwardSubst(|x, x)

forward-subst-assign =
Assign(?x, forward-subst => e)
; undefine-ForwardSubst(|x)
; if <not(is-var); is-pure-exp; not(contains(|Var(x)))> e then
where( innermost-scope-ForwardSubst => z )
; where( get-var-dependencies => deps )
; rules( ForwardSubst.z : Var(x) -> e depends on deps )
end

forward-subst-if =
IfElse(forward-subst, id, id)
; (IfElse(id, forward-subst, id) /ForwardSubst\ IfElse(id,id,forward-subst))

forward-subst-while =
?While(_, _)
; (/ForwardSubst\* While(forward-subst, forward-subst))

innermost-scope-ForwardSubst =
get-var-names => vars
; innermost-scope-ForwardSubst(elem-of(|vars))
```

## 7.7. Dead Code Elimination

Figure 7.10. file: til/xmpl/dce-test2

```sglri -p ../syn/TIL.tbl -i dce-test2.til |\
../sim/til-simplify |\
../opt/til-dce |\
ast2text -p ../pp/TIL-pretty.pp -o dce-test2.txt
```

Table 7.4. files: til/xmpl/dce-test2.til, til/xmpl/dce-test2.txt

beforeafter
```var x;
var y;
var z;
var a;
var b;
x := 1;
y := 2;
x := 3;
a := 7;
y := 3 + z;
if y then
z := 8;
x := 3;
else
x := 3;
z := 7 + z;
end
b := 7 + z;
z := 10;
writeint(b + 10);
```
```var y : int;
var z : int;
var b : int;
y := 3 + z;
if y then
z := 8;
else
z := 7 + z;
end
b := 7 + z;
write(int2string(b + 10));
```

Figure 7.11. file: til/opt/til-dce.str

```module til-dce
imports TIL til-eval liblib
rules

ElimDecl :
[Declaration(x) | st*] -> st*
where <not(VarUsed)> Var(x)

ElimDecl :
[DeclarationTyped(x, t) | st*] -> st*
where <not(VarUsed)> Var(x)

ElimAssign :
Assign(x, e) -> Block([])
where <not(VarNeeded)> Var(x)

ElimIf :
IfElse(e, [], []) -> Block([])

strategies

io-til-dce =
io-wrap(dce-program)

dce-stat =
ElimAssign
<+ dce-assign
<+ dce-proccall
<+ dce-if; try(ElimIf)
<+ dce-block
<+ dce-while

dce-program =
Program(dce-stats)

dce-block =
Block(dce-stats)

dce-stats =
dce-stats-decl
<+ dce-stats-other
<+ []

dce-stats-decl =
(?[Declaration(x) | _] <+ ?[DeclarationTyped(x, t) | _])
; {| VarNeeded, VarUsed
: rules(
VarNeeded+x :- Var(x)
VarUsed+x   :- Var(x)
)
; [id | dce-stats]
; try(ElimDecl)
|}

dce-stats-other =
[not(?Declaration(_) <+ ?DeclarationTyped(_, _)) | dce-stats]
; [dce-stat | id]
; try(?[Block([]) | <id>])

dce-assign =
?Assign(x, _)
; rules( VarNeeded.x :- Var(x) )
; Assign(id, declare-var-needed)

dce-proccall =
ProcCall(id, map(declare-var-needed))

declare-var-needed =
alltd({x :
?Var(x)
; rules(
VarNeeded.x : Var(x)
VarUsed.x   : Var(x)
)
})

dce-if =
?IfElse(_,_,_)
; (IfElse(id,dce-stats,id) /VarNeeded,VarUsed\ IfElse(id,id,dce-stats))
; IfElse(declare-var-needed, id, id)

dce-while =
?While(_, _)
; (\VarNeeded,VarUsed/* While(declare-var-needed, dce-stats))
```

## 7.8. Compiling the Transformations

Figure 7.12. file: til/opt/maak

```#! /bin/sh -e

INCL="-I ../sig -I ../sim"

# compile forward-subst
strc \${INCL} -i til-forward-subst.str -la stratego-lib -m io-til-forward-subst -O 2

# compile dce
strc \${INCL} -i til-dce.str -la stratego-lib -m io-til-dce -O 2

# compile cse
strc \${INCL} -i til-cse.str -la stratego-lib -m io-til-cse

# compile copyprop
strc -i til-copyprop.str \${INCL} -la stratego-lib -m io-til-copyprop

# compile copyprop-rev
strc -i til-copyprop-rev.str \${INCL} -la stratego-lib -m io-til-copyprop-rev

# compile propconst
strc -i til-propconst.str \${INCL} -la stratego-lib -m io-til-propconst
```