Posted to tcl by kbk at Mon Jan 13 20:12:06 GMT 2014view raw

  1. # revprop --
  2. #
  3. # "Reverse copy propagation"
  4. #
  5. # Parameters:
  6. # quads - Sequence of quadruples (three-address instructions)
  7. # vnames - List of variable names in order by variable indices
  8. #
  9. # Results:
  10. # Returns the given bytecode sequence, with unneeded code
  11. # elided.
  12. #
  13. # This pass functions as a cleanup for sequences that look like:
  14. #
  15. # v := ... A
  16. # v2 := v B
  17. # ... code that uses v2 ...
  18. #
  19. # The conditions for the optimization are:
  20. # all reachable uses of A: v:=... are copies of the form v2:=v
  21. # all reachable uses of A: v:=... copy to the same variable v2
  22. # no reachable use of A: v:=... has a reaching definition of v other than
  23. # A.
  24. #
  25. # In this case, the operation at A can be replaced with v2 :- ...,
  26. # and all the copies B can be elided
  27.  
  28. proc revprop {quads vnames} [bdd::datalog::compileProgram db {
  29. set dead {}
  30. } {
  31.  
  32. % An assignment of variable v at statement st can be replaced with
  33. % variable v2 to eliminate a copy of v to v2 at statement st2 if
  34. % there's no reason not to do so.
  35.  
  36. revprop(v, v2, st, st2) :- reaches(v, st, st2),
  37. isCopy(st2),
  38. writes0(st2, v2),
  39. !cantRevprop(v, v2, st).
  40.  
  41. % We cannot replace v with v2 in st if that would spoil any reachable
  42. % use of v or v2 from st.
  43.  
  44. cantRevprop(v, v2, st) :- reaches(v, st, st2), cantRevprop2(v, v2, st ,st2).
  45. cantRevprop(_, v2, st) :- flowsPast(v2, st, st2), reads0(st2, v2).
  46.  
  47. % A use of v in st2 is spoilt by this optimization if:
  48. % st2 isn't a copy,
  49. % st2 doesn't copy v to v2
  50. % st2 has a reaching definition of v that isn't st.
  51.  
  52. cantRevprop2(_, _, _, st2) :- !isCopy(st2).
  53. cantRevprop2(_, v2, _, st2) :- !writes0(st2, v2).
  54. cantRevprop2(v, _, st, st2) :- reaches(v, st3, st2), st3 != st.
  55.  
  56. revprop(v, v2, st, st2)?
  57.  
  58. } d {
  59. set v [lindex $vnames [dict get $d v]]
  60. set v2 [lindex $vnames [dict get $d v2]]
  61. set st [dict get $d st]
  62. set st2 [dict get $d st2]
  63. set q [lindex $quads $st]
  64. lset quads $st 1 $v2
  65. dict set dead $st2 {}
  66. } {
  67. # Remove the instructions that this optimization has killed
  68. tailcall quads-remove-dead $quads $dead
  69. }]
  70.