;; BF IR Optimization - Collapse Zeroes
;; Jon Simons (simonsj at ccs dot neu dot edu)
;; August, 2007
;; -------------------------------------------------------------------------
;; This module provides an optimization which collapses zero loops.
;;
;; Optimization:
;;
;;   This optimization looks for the brain-dead simple case of a LOOP or
;;   MUL with a single DEC expression whose pointer operand is the same as
;;   the LOOP's beginning pointer location.
;;
;;   (LOOP P (DEC 1 P)) --> (ZERO P)
;;
;;   (MUL P (DEC 1 P))  --> (ZERO P)
;;
;; -------------------------------------------------------------------------
(module collapse-zeroes mzscheme
  
  (require "../bf-ast-to-ir.scm")
  (provide collapse-zeroes)
  
  ;; Yields an IR tree whose collapsable zeroes are ZEROs.
  ;;
  ;; collapse-zeroes : (list of EXPRs) -> (list of EXPRs)
  (define (collapse-zeroes AST)
    (map (lambda (expr)
           (if (zero-loop? expr)
               (ZERO (EXPR-ptr expr))
               (if (EXPR-exprs expr)
                   (make-EXPR (EXPR-type expr)
                              (EXPR-N    expr)
                              (EXPR-ptr  expr)
                              (collapse-zeroes (EXPR-exprs expr)))
                   expr)))
         AST))
  
  ;; Determines whether the given EXPR is a "zero loop", where a
  ;; "zero loop" is simply defined as one of:
  ;;
  ;; (LOOP P            -or-          (MUL P
  ;;   (DEC 1 P))                       (DEC 1 P))
  ;;
  ;; Where P represents the same relative pointer location.
  ;;
  ;; zero-loop? : EXPR -> boolean
  (define (zero-loop? expr)
    (let ((ptr       (EXPR-ptr expr))
          (sub-exprs (EXPR-exprs expr))
          (type      (EXPR-type expr)))
      (and (or (eq? type 'loop)
               (eq? type 'mul))
           (=   (length sub-exprs) 1)
           (and (eq? (EXPR-type (car sub-exprs)) 'dec)
                (=   (EXPR-N    (car sub-exprs)) 1))
           (=   (EXPR-ptr  (car sub-exprs)) ptr))))
  
  )