Re: [?] Trees vs. Tuples for IRs

William D Clinger <will@ccs.neu.edu>
26 Sep 1998 01:45:11 -0400

          From comp.compilers

Related articles
[?] Trees vs. Tuples for IRs nshaf@intur.net (Nick Shaffner) (1998-09-13)
Re: [?] Trees vs. Tuples for IRs clark@quarry.zk3.dec.com (Chris Clark USG) (1998-09-18)
Re: [?] Trees vs. Tuples for IRs dwight@pentasoft.com (1998-09-18)
Re: [?] Trees vs. Tuples for IRs heinrich@idirect.com (1998-09-19)
Re: [?] Trees vs. Tuples for IRs cliff.click@Eng.Sun.COM (Clifford Click) (1998-09-22)
Re: [?] Trees vs. Tuples for IRs will@ccs.neu.edu (William D Clinger) (1998-09-26)
Re: [?] Trees vs. Tuples for IRs pmk@sgi.com (Peter Klausler) (1998-09-26)
| List of all articles for this month |

From: William D Clinger <will@ccs.neu.edu>
Newsgroups: comp.compilers
Date: 26 Sep 1998 01:45:11 -0400
Organization: Northeastern University
References: 98-09-042 98-09-064 98-09-108
Keywords: design, optimize

I prefer trees for interprocedural optimizations (which includes
loop optimizations in Scheme) and tuples for more local optimizations.


A-normal form is a kind of compromise between the two. I guess it
would be kind of crummy to mention this without giving an example,
so see below.


Will


----


; Original Scheme code.


(define (remove a x)
    (define (loop x y)
        (cond ((null? x) y)
                    ((not (equal? a (car x)))
                      (loop (cdr x)
                                  (cons (car x) y)))
                    (else
                      (loop (cdr x) y))))
    (loop (reverse x) '()))


; A-normal form, after actuals have been mapped to registers.


(let* ((.T20
                (lambda (.a_2 .x_2)
                    (define .loop_3
                        (lambda (..a_2_15 .x_5 .y_5)
                            (let ((.T5 (null? .x_5)))
                                (if .T5
                                        .y_5
                                        (let* ((.REG1 ..a_2_15)
                                                      (.REG2 (car .x_5))
                                                      (.T9 (equal? .REG1 .REG2)))
                                            (if .T9
                                                    (let* ((.REG3 .y_5)
                                                                  (.REG1 ..a_2_15)
                                                                  (.REG2 (cdr:pair .x_5)))
                                                        (.loop_3 .REG1 .REG2 .REG3))
                                                    (let* ((.REG1 ..a_2_15)
                                                                  (.T15 (car:pair .x_5))
                                                                  (.REG3 (cons .T15 .y_5))
                                                                  (.REG2 (cdr:pair .x_5)))
                                                        (.loop_3 .REG1 .REG2 .REG3))))))))
                    (define .T19 (lambda (..a_2_3 ..x_2_3)
                                                  (let* ((.REG1 ..x_2_3)
                                                                (.T2 (reverse .REG1))
                                                                (.REG1 ..a_2_3)
                                                                (.REG2 .T2))
                                                      (.loop_3 .REG1 .REG2 '()))))
                    (let* ((.REG1 .a_2) (.REG2 .x_2))
                        (.T19 .REG1 .REG2))))
              (.U22 (set! remove .T20)))
    'remove)


--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.