From c3174f915dbcd5cd90659279671b9a3005b840ea Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Sat, 27 Feb 2021 11:53:25 -0800 Subject: 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. --- share/txr/stdlib/compiler.tl | 1 + share/txr/stdlib/optimize.tl | 18 ++++++++++++++++++ 2 files changed, 19 insertions(+) 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 -- cgit v1.2.3