src/compiler/dce.lisp

   1 ;;;; This file implements a dead-code elimination phase for the
   2 ;;;; compiler.  We perform a flow-sensitive analysis of a component
   3 ;;;; from a set of externally-referenced CLAMBDAs, finding all
   4 ;;;; reachable blocks, and delete any unreferenced CLAMBDAs and
   5 ;;;; blocks.
   6
   7 (in-package "SB!C")
   8 \f
   9 ;;; A CLAMBDA is deemed to be "externally referenced" if:
  10 ;;;   - It is of KIND :TOPLEVEL (a toplevel CLAMBDA).
  11 ;;;   - It is of KIND :OPTIONAL (an OPTIONAL-DISPATCH entry point,
  12 ;;;     which may not be deleted even if it is not referenced).
  13 ;;;   - It is LAMBDA-HAS-EXTERNAL-REFERENCES-P true (from COMPILE
  14 ;;;     or from the fopcompiler, possibly other causes).
  15 ;;;   - It has a REF which has a NODE-COMPONENT other than the
  16 ;;;     LAMBDA-COMPONENT of the CLAMBDA.
  17 ;;;
  18 ;;; Arranging for CLAMBDAs of KIND :TOPLEVEL to be set
  19 ;;; LAMBDA-HAS-EXTERNAL-REFERENCES-P true is trivial, but doesn't gain
  20 ;;; us overmuch.  Arranging for the REF-based check to be cached or
  21 ;;; optimistically computed might gain us more, but is not trivial to
  22 ;;; implement.
  23 (defun lambda-externally-referenced-p (clambda)
  24   (or (lambda-has-external-references-p clambda)
  25       (member (lambda-kind clambda) '(:toplevel :optional))
  26       (let ((home-component (lambda-component clambda)))
  27         (some (lambda (ref)
  28                 (not (eq (node-component ref)
  29                          home-component)))
  30               (lambda-refs clambda)))))
  31 \f
  32 (defun dce-analyze-ref (ref)
  33   (let ((leaf (ref-leaf ref)))
  34     (typecase leaf
  35       (clambda
  36        ;; If a CLAMBDA points to this component, mark its blocks as
  37        ;; being live.
  38        ;;
  39        ;; FLUSH-DEAD-CODE is supposed to have killed :ZOMBIE CLAMBDAs
  40        ;; (see commentary on DELETE-LET in IR1OPT), but may not have
  41        ;; run yet, or may not have been able to kill the CLAMBDA in
  42        ;; question, but the LAMBDA-BIND would be NIL, so just ignore
  43        ;; :DELETED and :ZOMBIE CLAMBDAs here.
  44        (unless (member (functional-kind leaf)
  45                        '(:deleted :zombie))
  46          (when (eq (lambda-component leaf)
  47                    (node-component ref))
  48            (dce-analyze-one-fun leaf))))
  49       ;; KLUDGE: Pick off CONSTANTs that have an NLX-INFO as the value
  50       ;; in order to find the NLX entry blocks.  Should probably be
  51       ;; checking for COMBINATIONs of %UNWIND-PROTECT and %CATCH
  52       ;; instead.
  53       (constant
  54        (let ((value (constant-value leaf)))
  55          (when (and (nlx-info-p value)
  56                     (nlx-info-target value))
  57            (dce-analyze-block (nlx-info-target value))))))))
  58
  59 (defun dce-analyze-block (block)
  60   (unless (block-flag block)
  61     (setf (block-flag block) t)
  62
  63     (do-nodes (node nil block)
  64       (typecase node
  65         (ref
  66          (dce-analyze-ref node))))
  67
  68     (dolist (succ (block-succ block))
  69       (dce-analyze-block succ))))
  70
  71 (defun dce-analyze-one-fun (clambda)
  72   (dce-analyze-block
  73    (node-block
  74     (lambda-bind clambda))))
  75 \f
  76 (defun eliminate-dead-code (component)
  77   (clear-flags component)
  78
  79   (dolist (fun (component-lambdas component))
  80     (when (lambda-externally-referenced-p fun)
  81       (dce-analyze-one-fun fun)))
  82
  83   ;; For reasons that I completely fail to ascertain, simply calling
  84   ;; DELETE-BLOCK directly messes up FIND-DFO, as does calling
  85   ;; DELETE-BLOCK-LAZILY followed by a CLEAN-COMPONENT, but calling
  86   ;; DELETE-BLOCK-LAZILY followed by FIND-DFO seems to work.  -- AJB,
  87   ;; 2014-Jun-08
  88   (do-blocks (block component)
  89     (unless (block-flag block)
  90       (delete-block-lazily block)))
  91   (find-dfo component))