dce.scm

;;; SonicBoom — tracing prototype: dead-node elimination
;;;
;;; SPDX-License-Identifier: GPL-3.0-or-later
;;; Copyright (C) 2026 Nala Ginrut <roy@hardenedlinux.org>
;;;
;;; One backward pass from the segment's outputs. A node is live iff it is
;;; effectful (e.g. `print`) or one of its outputs is live; a parameter is live
;;; iff a live node or a graph output references it.

(define-module (sonicboom trace dce)
  #:use-module (srfi srfi-1)
  #:use-module (sonicboom trace compat)
  #:use-module (sonicboom trace graph)
  #:use-module (sonicboom trace ops)
  #:export (eliminate-dead-nodes))

(define (eliminate-dead-nodes nodes params outputs)
  "NODES in topological order, PARAMS a list of gparams, OUTPUTS the value
names that must survive. Returns (values live-nodes live-params), both in
their original order."
  (let ((live (make-table)))
    (for-each (lambda (o) (table-set! live o #t)) outputs)
    (let ((kept
           (fold (lambda (n acc)
                   (if (or (op-effectful? (gnode-op n))
                           (any (lambda (o) (table-ref live o #f))
                                (gnode-output-names n)))
                       (begin
                         (for-each (lambda (i) (table-set! live i #t))
                                   (gnode-inputs n))
                         (cons n acc))
                       acc))
                 '()
                 (reverse nodes))))
      (values kept
              (filter (lambda (p) (table-ref live (gparam-name p) #f)) params)))))