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