Posted to tcl by kbk at Wed Jan 08 23:32:55 GMT 2014view raw

  1. set vars [analyzeProgram $program db]
  2. set vnames [dict keys $vars]
  3.  
  4. db relation seq st st2
  5. db relation writes st v
  6. db relation flowspast v st st2
  7. db relation reaches v st st2
  8. db relation uninitRead st v
  9. db relation deadWrite st v
  10. # db relation induction v st
  11.  
  12. proc reaching_defs {} [bdd::datalog::compileProgram db {
  13.  
  14. % A false entry node (node 0) sets every variable and flows
  15. % to node 1. If any of its variables are reachable, those are
  16. % variables possibly used uninitialized in the program.
  17.  
  18. writes(0, _).
  19. writes(st,v) :- writes0(st,v).
  20. seq(0, 1).
  21. seq(st,st2) :- seq0(st,st2).
  22.  
  23. % flowspast(v,st,st2) means that control passes from the exit of st
  24. % to the entry of st2 without altering the value of v
  25.  
  26. flowspast(_, st, st2) :- seq(st, st2).
  27. flowspast(v, st3, st2) :- flowspast(v, st3, st),
  28. !writes(st, v),
  29. flowspast(v, st, st2).
  30.  
  31. % reaches(v,st,st2) means that st assigns a value to v, which
  32. % reaches st2, which reads the value of v : that is, st is a
  33. % reaching definition for the use of v at st2.
  34.  
  35. reaches(v, st, st2) :- writes(st, v), flowspast(v, st, st2), reads(st2, v).
  36.  
  37. % A variable read that is reachable from the entry is a read of a
  38. % possibly uninitialized variable
  39.  
  40. uninitRead(st, v) :- reaches(v, 0, st).
  41.  
  42. % A variable write that reaches nowhere else is dead code
  43.  
  44. deadWrite(st, v) :- writes(st, v), !reaches(v, st, _).
  45.  
  46. }]
  47.  
  48. # Report which variable definitions reach statement $i
  49. proc query1 {i} [bdd::datalog::compileProgram db {
  50. reaches(v, st, $i)?
  51. } d {
  52. lappend ::flowsto [lindex $::vnames [dict get $d v]] [dict get $d st]
  53. }]
  54.  
  55. # Report which variable uses flow from statement $i
  56. proc query2 {i} [bdd::datalog::compileProgram db {
  57. reaches(v, $i, st)?
  58. } d {
  59. lappend ::flowsfrom [lindex $::vnames [dict get $d v]] [dict get $d st]
  60. }]
  61.  
  62.  
  63. reaching_defs
  64.  
  65. puts [format {%-16s %2s %-32s %-16s} PRODUCERS {} INSTRUCTIONS CONSUMERS]
  66. set i 0
  67. foreach stmt $program {
  68. set flowsto {}
  69. query1 $i
  70. set flowsfrom {}
  71. query2 $i
  72. puts [format "%-16s %2d: %-32s %-16s" \
  73. [lsort -stride 2 -index 0 -ascii \
  74. [lsort -stride 2 -index 1 -integer $flowsto]] \
  75. $i \
  76. $stmt \
  77. [lsort -stride 2 -index 0 -ascii \
  78. [lsort -stride 2 -index 1 -integer $flowsfrom]]]
  79. incr i
  80. }