Chapter 7. Data-flow Transformation (*)

Chapter 7. Data-flow Transformation (*)
Prev	Part I. A Tiny Imperative Language	Next

Table of Contents

7.1. Preliminaries
7.2. Constant Propagation
7.3. Copy Propagation
7.4. Reverse Copy Propagation
7.5. Common-subexpression Elimination
7.6. Forward Substitution
7.7. Dead Code Elimination
7.8. Compiling the Transformations

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

before	after
var x; var y; var z; var a; var b; z := readint(); 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; z := string2int(read()); 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));

before

after

var x; 
var y;
var z; 
var a; 
var b;
z := readint();
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;
z := string2int(read());
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

before	after
var x : int; var y : int; x := string2int(read()); y := x; y := y + 1; x := y; write(int2string(x));	var x : int; var y : int; x := string2int(read()); 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

before	after
var a; var b; var x; a := readint(); b := readint(); x := a + b; writeint(a + b); a := 23; x := a + b; writeint(a + b);	var a : int; var b : int; var x : int; a := string2int(read()); b := string2int(read()); x := a + b; write(int2string(x)); a := 23; x := a + b; write(int2string(x));

before

after

var a;
var b;
var x;
a := readint();
b := readint();
x := a + b;
writeint(a + b);
a := 23;
x := a + b;
writeint(a + b);

var a : int;
var b : int;
var x : int;
a := string2int(read());
b := string2int(read());
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

before	after
var x; var y; var z; var a; var b; z := readint(); 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; z := string2int(read()); y := 3 + z; if y then z := 8; else z := 7 + z; end b := 7 + z; write(int2string(b + 10));

before

after

var x;
var y;
var z;
var a;
var b;
z := readint();
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;
z := string2int(read());
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

Prev	Up	Next
Chapter 6. Interpretation	Home	Chapter 8. Typestate Checking