Need to reverse order of constant propagation and specialization
Marc: Consider the following code: (declare (standard-bindings)(extended-bindings)(block)) (define (expt1 a b) (define (square x) (* x x)) (cond ((= b 0) 1) ((even? b) (square (expt1 a (quotient b 2)))) (else (* a (square (expt1 a (quotient b 2))))))) (declare (inlining-limit 100000)) (define a (expt1 2 20)) (define b (expt1 2 40)) (define c (expt1 2 80)) When compiled, this gives peano-71% gsc -c -expansion crap loading /pkgs/Gambit-C/gambcext.scm Expansion: (define expt1 (lambda (a b) (if (if (and (##fixnum? b) #t) (##fixnum.= b 0) (= b 0)) 1 (if (even? b) (let ((x (expt1 a (or (and (##fixnum? b) (##fixnum.quotient? b 2)) (quotient b 2))))) (or (and (##fixnum? x) (and (##fixnum? x) (##fixnum.*? x x))) (* x x))) (let ((temp (let ((x (expt1 a (or (and (##fixnum? b) (##fixnum.quotient? b 2)) (quotient b 2))))) (or (and (##fixnum? x) (and (##fixnum? x) (##fixnum.*? x x))) (* x x))))) (or (and (##fixnum? a) (and (##fixnum? temp) (##fixnum.*? a temp))) (* a temp))))))) (define a 1048576) (define b (or (##fixnum.*? 1048576 1048576) 1099511627776)) (define c (let ((x (or (##fixnum.*? 1048576 1048576) 1099511627776))) (or (and (##fixnum? x) (and (##fixnum? x) (##fixnum.*? x x))) (* x x)))) Note how a is completely determined, b has the code it has because (##fixnum.*? 1048576 1048576) could be #t or #f depending on whether Gambit was compiled for 32-bit or 64-bit machines, etc. It seems that the expansion of *, +, etc., was done before the constant propagation and evaluation of known functions. This should be reversed, and a, b, and c should all be reduced to constants in the compile. Brad
Afficher les réponses par date
On Jun 26, 2005, at 12:03 AM, Bradley Lucier wrote:
Marc:
Consider the following code:
(declare (standard-bindings)(extended-bindings)(block))
(define (expt1 a b) (define (square x) (* x x)) (cond ((= b 0) 1) ((even? b) (square (expt1 a (quotient b 2)))) (else (* a (square (expt1 a (quotient b 2)))))))
(declare (inlining-limit 100000))
(define a (expt1 2 20))
(define b (expt1 2 40))
(define c (expt1 2 80))
When compiled, this gives
(define expt1 (lambda (a b) (if (if (##fixnum? b) (##fixnum.= b 0) (= b 0)) 1 (if (even? b) (let ((x (expt1 a (if (and (##fixnum? b) #t) (##fixnum.quotient b 2) (quotient b 2))))) (if (and (##fixnum? x) (##fixnum? x)) (if (##fixnum.= x 0) 0 (let ((temp (if (##fixnum.= x -1) (##fixnum.-? x) (##fixnum.*? x x)))) (if temp temp (* x x)))) (* x x))) (let ((temp (let ((x (expt1 a (if (and (##fixnum? b) #t) (##fixnum.quotient b 2) (quotient b 2))))) (if (and (##fixnum? x) (##fixnum? x)) (if (##fixnum.= x 0) 0 (let ((temp (if (##fixnum.= x -1) (##fixnum.-? x) (##fixnum.*? x x)))) (if temp temp (* x x)))) (* x x))))) (if (and (##fixnum? temp) (##fixnum? a)) (if (##fixnum.= temp 0) 0 (let ((temp#1 (if (##fixnum.= temp -1) (##fixnum.-? a) (##fixnum.*? a temp)))) (if temp#1 temp#1 (* a temp)))) (* a temp))))))) (define a 1048576) (define b (let ((temp (##fixnum.*? 1048576 1048576))) (if temp temp 1099511627776))) (define c (let ((x (let ((temp (##fixnum.*? 1048576 1048576))) (if temp temp 1099511627776)))) (if (and (##fixnum? x) (##fixnum? x)) (if (##fixnum.= x 0) 0 (let ((temp (if (##fixnum.= x -1) (##fixnum.-? x) (##fixnum.*? x x)))) (if temp temp (* x x)))) (* x x)))) So the problem noticed for beta13 is still there---you need to do partial evaluation/constant propagation *before* specializing the functions for fixnum values. Some other comments about the generated code: 1. (even? b) and (odd? b) can be specialized for fixnum. 2. The following don't look very good: (let ((temp (let ((x (expt1 a (if (and (##fixnum? b) #t) ;;; <<<<<<<<<<< (##fixnum.quotient b 2) (quotient b 2))))) (if (and (##fixnum? x) (##fixnum? x)) ;;; <<<<<<<<<<< ... I guess the first happens because (quotient x y) is expanded to (let ((temp y)) (if (and (##fixnum? temp) (and (##fixnum? x) (##not (##fixnum.= temp 0)))) (if (##fixnum.= temp -1) (or (##fixnum.-? x) (quotient x temp)) (##fixnum.quotient x temp)) (quotient x temp))) and when temp=2, (##fixnum? temp) and (##not (##fixnum.= temp 0)) both evaluate to #t and (##fixnum.= temp -1) evaluates to #f. And unfortunately, the adjacent fixnum tests do appear in the C code. (Perhaps gcc eliminates them, I didn't check the assembly.) 3. The code goes on to (if (##fixnum.= x 0) 0 (let ((temp (if (##fixnum.= x -1) (##fixnum.-? x) ;;; <<<<<<<<< (##fixnum.*? x x)))) Here it should just return 1. (This happens with (* x x)) But overall, very nice. Brad
participants (1)
-
Bradley Lucier