diff options
author | Kaz Kylheku <kaz@kylheku.com> | 2021-02-27 11:53:25 -0800 |
---|---|---|
committer | Kaz Kylheku <kaz@kylheku.com> | 2021-02-27 11:53:25 -0800 |
commit | c3174f915dbcd5cd90659279671b9a3005b840ea (patch) | |
tree | 2441e775f44f5dc929d7ea0e376f56b44254ddd0 | |
parent | 8a90bf63fafe544c990519282f054f72f3e866f4 (diff) | |
download | txr-c3174f915dbcd5cd90659279671b9a3005b840ea.tar.gz txr-c3174f915dbcd5cd90659279671b9a3005b840ea.tar.bz2 txr-c3174f915dbcd5cd90659279671b9a3005b840ea.zip |
compiler: add dead code elimination pass.
* share/txr/stdlib/compiler.tl (compiler optimize): Call new
elim-dead-code method on basic-blocks object.
* share/txr/stdlib/optimize.tl (basic-blocks elim-dead-code):
New method. We reset the links information for each basic
block and re-build the graph. Then we traverse it to determine
what blocks are reachable, and cull the original blocks list
of those that are not.
-rw-r--r-- | share/txr/stdlib/compiler.tl | 1 | ||||
-rw-r--r-- | share/txr/stdlib/optimize.tl | 18 |
2 files changed, 19 insertions, 0 deletions
diff --git a/share/txr/stdlib/compiler.tl b/share/txr/stdlib/compiler.tl index 1d95fd3b..4d08b526 100644 --- a/share/txr/stdlib/compiler.tl +++ b/share/txr/stdlib/compiler.tl @@ -1506,6 +1506,7 @@ bb.(calc-liveness) bb.(peephole) bb.(thread-jumps) + bb.(elim-dead-code) bb.(get-insns))) (defun true-const-p (arg) diff --git a/share/txr/stdlib/optimize.tl b/share/txr/stdlib/optimize.tl index 754ad9ae..259a64ae 100644 --- a/share/txr/stdlib/optimize.tl +++ b/share/txr/stdlib/optimize.tl @@ -388,6 +388,24 @@ (dohash (label bl bb.hash) (set bl.insns bb.(thread-jumps-block label bl.insns)))) +(defmeth basic-blocks elim-dead-code (bb) + (dohash (label bl bb.hash) + (set bl.links nil)) + bb.(link-graph) + (let* ((visited (hash :eq-based)) + (reachable (build + (labels ((visit (bl) + (when (test-set [visited bl]) + (add bl.label) + (when bl.next + (visit [bb.hash bl.next])) + [mapcar [chain bb.hash visit] bl.links]))) + (for ((bl bb.root)) (bl) ((set bl [bb.hash bl.next])) + (add bl.label) + (visit bl)) + (visit bb.root))))) + (set bb.labels [keep-if (chain bb.hash visited) bb.labels]))) + (defun rewrite (fun list) (build (while* list |