;; BF IR Optimization - Dead Loop Elimination
;; Jon Simons (simonsj at ccs dot neu dot edu)
;; April, 2008
;; -------------------------------------------------------------------------
;; This module provides an optimization which eliminates dead loops.
;;
;; I ran across the idea for this optimization while looking at the AWIB
;; compiler, located here:
;;   http://www.nada.kth.se/~matslina/awib/
;;
;; Optimization:
;;
;;   This optimization removes dead loops from a program's AST.  There
;;   are two cases of loops which can be statically determined to never
;;   execute:
;;
;;     A loop that begins a BF program will never be entered (all cells
;;     are zero).
;;
;;         (list (LOOP...) <EXPRs>)  --->  (list <EXPRs>)
;;
;;     Any loop immediately following another loop that has no 'lefts' or
;;     'rights' will never be executed (because the 'current' value will be
;;     zero upon loop exit).
;;
;;         (list ... (LOOP1 ...) (LOOP2 ...) ...)
;;
;;           --->  (list ... (LOOP1 ...) <EXPRs>...)
;;
;; -------------------------------------------------------------------------
(module dead-loops mzscheme
  
  (require "../bf-ast-to-ir.scm")
  (provide kill-dead-loops)
  
  ;; Is the given expr an elligible loop for being dead?
  (define (loop-elligible? expr)
    (and (eq? (EXPR-type expr) 'loop)
         (=   (EXPR-ptr expr)  0)))
  
  ;; Prunes the given IR tree of dead loops.
  ;;
  ;; kill-dead-loops : (list of EXPRs) -> (list of EXPRs)
  (define (kill-dead-loops AST)
    (letrec ((kdl (lambda (exprs prev-expr-loop? acc)
                    (if (null? exprs)
                        acc
                        (let* ((e     (car exprs))
                               (loop? (loop-elligible? e)))
                          (if (and prev-expr-loop? loop?)
                              (kdl (cdr exprs) #t acc)
                              (kdl (cdr exprs) loop? (cons e acc))))))))
      (reverse (kdl AST #t null))))
  
  )