source: project/chicken/branches/scrutiny/scrutinizer.scm @ 13968

Last change on this file since 13968 was 13968, checked in by felix winkelmann, 11 years ago

a few fixes

File size: 16.9 KB
Line 
1;;;; scrutinizer.scm - The CHICKEN Scheme compiler (local flow analysis)
2;
3; Copyright (c) 2009, The Chicken Team
4; All rights reserved.
5;
6; Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
7; conditions are met:
8;
9;   Redistributions of source code must retain the above copyright notice, this list of conditions and the following
10;     disclaimer.
11;   Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following
12;     disclaimer in the documentation and/or other materials provided with the distribution.
13;   Neither the name of the author nor the names of its contributors may be used to endorse or promote
14;     products derived from this software without specific prior written permission.
15;
16; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
17; OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
18; AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
19; CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20; CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21; SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
23; OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24; POSSIBILITY OF SUCH DAMAGE.
25
26
27(declare (unit scrutinizer))
28
29(private compiler
30  compiler-arguments process-command-line perform-lambda-lifting!
31  default-standard-bindings default-extended-bindings
32  foldable-bindings llist-length
33  installation-home decompose-lambda-list external-to-pointer
34  copy-node! variable-visible? mark-variable intrinsic?
35  unit-name insert-timer-checks used-units external-variables hide-variable
36  debug-info-index debug-info-vector-name profile-info-vector-name
37  foreign-declarations emit-trace-info block-compilation line-number-database-size
38  make-block-variable-literal block-variable-literal? block-variable-literal-name
39  target-heap-size target-stack-size constant-declarations variable-mark
40  default-default-target-heap-size default-default-target-stack-size verbose-mode original-program-size
41  current-program-size line-number-database-2 foreign-lambda-stubs immutable-constants foreign-variables
42  rest-parameters-promoted-to-vector inline-table inline-table-used constant-table constants-used
43  broken-constant-nodes inline-substitutions-enabled loop-lambda-names expand-profile-lambda
44  profile-lambda-list profile-lambda-index emit-profile expand-profile-lambda
45  direct-call-ids foreign-type-table first-analysis expand-debug-lambda expand-debug-assignment expand-debug-call
46  initialize-compiler canonicalize-expression expand-foreign-lambda update-line-number-database! scan-toplevel-assignments
47  perform-cps-conversion analyze-expression simplifications perform-high-level-optimizations perform-pre-optimization!
48  reorganize-recursive-bindings substitution-table simplify-named-call compiler-warning
49  perform-closure-conversion prepare-for-code-generation compiler-source-file create-foreign-stub expand-foreign-lambda*
50  transform-direct-lambdas! expand-foreign-callback-lambda* debug-lambda-list debug-variable-list debugging
51  debugging-chicken bomb check-signature posq stringify symbolify build-lambda-list
52  string->c-identifier c-ify-string words check-and-open-input-file close-checked-input-file fold-inner constant?
53  collapsable-literal? immediate? canonicalize-begin-body extract-mutable-constants string->expr get get-all
54  put! collect! count! get-line get-line-2 find-lambda-container display-analysis-database varnode qnode 
55  build-node-graph build-expression-tree fold-boolean inline-lambda-bindings match-node expression-has-side-effects?
56  simple-lambda-node? compute-database-statistics print-program-statistics output gen gen-list 
57  pprint-expressions-to-file foreign-type-check estimate-foreign-result-size scan-used-variables scan-free-variables
58  topological-sort print-version print-usage initialize-analysis-database
59  expand-foreign-callback-lambda default-optimization-passes default-optimization-passes-when-trying-harder
60  units-used-by-default words-per-flonum rewrite inline-locally
61  parameter-limit eq-inline-operator optimizable-rest-argument-operators
62  membership-test-operators membership-unfold-limit valid-compiler-options valid-compiler-options-with-argument
63  make-random-name final-foreign-type inline-max-size simplified-ops
64  generate-code make-variable-list make-argument-list generate-foreign-stubs foreign-type-declaration
65  foreign-argument-conversion foreign-result-conversion foreign-type-convert-argument foreign-type-convert-result
66  scrutinize load-type-database)
67
68
69(include "tweaks")
70
71
72(define-syntax d
73  (syntax-rules ()
74    ((_ fstr args ...)
75     (printf "[debug] ~?~%" fstr (list args ...)))))
76
77
78;;; Walk node tree, keeping type and binding information
79;
80; result specifiers:
81;
82;   SPEC = * | (VAL1 ...)
83;   VAL = (or VAL1 ...)
84;       | (struct NAME)
85;       | (procedure (VAL1 ... [#!rest [VAL]]) . RESULTS)
86;       | BASIC
87;   BASIC = * | string | symbol | char | number | boolean | list | pair | procedure | vector | void | null | eof | undefined
88;   RESULTS = *
89;           | (VAL1 ...)
90
91; global symbol properties:
92;
93;   ##core#type           ->  <typespec>
94;   ##core#declared-type  ->  <bool>
95
96(define-constant +fragment-max-length+ 5)
97
98(define (scrutinize node db)
99  (define (constant-result lit)
100    (cond ((string? lit) 'string)
101          ((symbol? lit) 'symbol)
102          ((number? lit) 'number)
103          ((boolean? lit) 'boolean)
104          ((list? lit) 'list)
105          ((pair? lit) 'pair)
106          ((boolean? lit) 'boolean)
107          ((eof-object? lit) 'eof)
108          ((vector? lit) 'vector)
109          ((##sys#generic-structure? lit) `(struct ,(##sys#slot lit 0)))
110          ((null? lit) 'null)
111          ((char? lit) 'char)
112          (else '*)))
113  (define (global-result id)
114    (cond ((##sys#get id '##core#type) =>
115           (lambda (a) 
116             (cond ((and (get db id 'assigned)
117                         (not (##sys#get id '##core#declared-type)))
118                    (##sys#put! id '##core#type #f)
119                    '*)
120                   (else (list a)))))
121          (else '*)))
122  (define (variable-result id e)
123    (cond ((and (get db id 'assigned) 
124                (not (##sys#get id '##core#declared-type)) )
125           '*)
126          ((assq id e) =>
127           (lambda (a) (list (cdr a))))
128          (else (global-result id))))
129  (define (always-true t loc x)
130    (let ((f (cond ((and (pair? t) (eq? 'or (car t)))
131                    (every (cut always-true <> loc x) (cdr t)))
132                   ((memq t '(* boolean undefined)) #f)
133                   (else #t))))
134      (when f
135        (report 
136         loc "of type boolean" "a result that is always true" 
137         "value"
138         (sprintf "in conditional `~s'," (fragment x))))
139      f))
140  (define (typename t)
141    (case t
142      ((*) "anything")
143      ((char) "character")
144      (else
145       (cond ((symbol? t) (symbol->string t))
146             ((pair? t)
147              (case (car t)
148                ((procedure) 
149                 (if (or (string? (cadr t)) (symbol? (cadr t)))
150                     (->string (cadr t))
151                     (sprintf "a procedure with ~a returning ~a"
152                              (argument-string (cadr t))
153                              (result-string (cddr t)))))
154                ((or)
155                 (string-intersperse
156                  (map typename (cdr t))
157                  " OR "))
158                ((struct)
159                 (sprintf "a structure of type ~a" (cadr t)))
160                (else (bomb "invalid type: ~a" t))))
161             (else (bomb "invalid type: ~a" t))))))
162  (define (argument-string args)
163    (let ((len (length args))
164          (m (multiples len)))
165      (if (zero? len)
166          "zero arguments"
167          (sprintf 
168           "~a argument~a of type~a ~a"
169           len m m
170           (map typename args)))))
171  (define (result-string results)
172    (if (eq? '* results) 
173        "an unknown number of values"
174        (let ((len (length results))
175              (m (multiples len)))
176          (if (zero? len)
177              "zero values"
178              (sprintf 
179               "~a value~a of type~a ~a"
180               len m m
181               (map typename results))))))
182  (define (simplify t)
183    (let ((t2 (simplify1 t)))
184      (d "simplify: ~a -> ~a" t t2)
185      t2))
186  (define (simplify1 t)
187    (if (pair? t)
188        (case (car t)
189          ((or)
190           (if (= 2 (length t))
191               (simplify (second t))
192               (let* ((ts (append-map
193                           (lambda (t)
194                             (let ((t (simplify t)))
195                               (if (and (pair? t) (eq? 'or (car t)))
196                                   (cdr t)
197                                   (list t))))
198                           (cdr t)))
199                     (ts2 (let loop ((ts ts))
200                            (cond ((null? ts) '())
201                                  ((any (cut match (car ts) <>) (cdr ts))
202                                   (loop (cdr ts)))
203                                  (else (cons (car ts) (loop (cdr ts))))))))
204                 (d "  or-simplify: ~a" ts2)
205                 (simplify `(or ,@(if (any (cut eq? <> '*) ts2) '(*) ts2))))))
206          ((procedure)
207           (let ((name (and (not (list? (cadr t))) (cadr t))))
208             `(procedure 
209               ,@(if name (list name) '())
210               ,(map simplify (second t))
211               ,@(map simplify (cddr t)))))
212          (else t))
213        t))
214  (define (match t1 t2)
215    (let ((m (match1 t1 t2)))
216      (d "match ~a <-> ~a -> ~a" t1 t2 m)
217      m))
218  (define (match1 t1 t2)
219    (or (eq? t1 t2)
220        (eq? t1 '*)
221        (eq? t2 '*)
222        (and (eq? 'procedure t1) (and (pair? t2) (eq? 'procedure (car t2)))
223             (eq? 'procedure t2) (and (pair? t1) (eq? 'procedure (car t1))) )
224        (and (pair? t1) (pair? t2)
225             (or (and (eq? (car t1) 'or)
226                      (any (cut match <> t2)))
227                 (and (eq? (car t2) 'or)
228                      (any (cut match <> t2)))
229                 (or (eq? (car t1) (car t2))
230                     (and (eq? 'procedure (car t1))
231                          (let ((args1 (if (pair? (second t1)) (second t1) (third t1)))
232                                (args2 (if (pair? (second t2)) (second t2) (third t2))) 
233                                (results1 (if (pair? (second t2)) (cdddr t2) (cddr t2))) 
234                                (results2 (if (pair? (second t2)) (cdddr t2) (cddr t2))) )
235                            (and (match-args args1 args2)
236                                 (= (length results1) (length results2))
237                                 (every match results1 results2))))
238                     (and (eq? 'struct (car t1))
239                          (equal? t1 t2)))))))
240  (define (match-args args1 args2)
241    (define (match-rest rtype args)
242      (let-values (((head tail) (break (cut eq? '#!rest <>) args)))
243        (and (every (cut match rtype <>) head) ; match required args
244             (match
245              rtype
246              (if (and (pair? tail) (pair? (cdr tail)))
247                  (cadr tail)
248                  '*) ) ) ) )
249    (let loop ((args1 args1) (args2 args2))
250      (cond ((null? args1) 
251             (or (null? args2)
252                 (eq? '#!rest (car args2))))
253            ((null? args2)
254             (eq? '#!rest (car args2)))
255            ((eq? '#!rest (car args1))
256             (match-rest (if (pair? (cdr args1)) (cadr args1) '*) args2))
257            ((eq? '#!rest (car args2))
258             (match-rest (if (pair? (cdr args2)) (cadr args2) '*) args1))
259            ((match (car args1) (car args2)) (loop (cdr args1) (cdr args2)))
260            (else #f))))
261  (define (check expected given loc what #!optional desc) 
262    (d "check: ~a <-> ~a (~a)" expected given loc)
263    (if (match expected given)
264        given
265        (report loc expected given what desc)))
266  (define (multiples n)
267    (if (= n 1) "" "s"))
268  (define (single tv loc)
269    (if (eq? '* tv)
270        '*
271        (let ((n (length tv)))
272          (cond ((= 1 n) (car tv))
273                ((zero? n)
274                 (report loc "a single result" "zero results" #f)
275                 'void)
276                (else
277                 (report loc "a single result" (sprintf "~a result~a" n (multiples n)) #f)
278                 (first tv))))))
279  (define (report1 loc desc)
280    (compiler-warning
281     'scrutiny
282     "~a~a" 
283     (location-name loc) desc))
284  (define (report loc expected given what #!optional desc)
285    (report1 
286     loc 
287     (sprintf 
288      "~a~a~a~a"
289      (or desc "")
290      (if desc " " "")
291      (if expected
292          (sprintf "expected ~a~a~a" (or what "") (and what " ") expected)
293          "")
294      (sprintf ", but where given ~a" given))))
295  (define (location-name loc)
296    (define (lname loc1)
297      (if loc1
298          (sprintf "procedure `~s'" loc1)
299          "unknown procedure"))
300    (cond ((null? loc) "at toplevel:\n")
301          ((null? (cdr loc))
302           (sprintf "in toplevel ~a" (lname (car loc)) ":\n"))
303          (else
304           (let rec ((loc loc))
305             (if (null? (cdr loc))
306                 (string-append (location-name loc) ":\n")
307                 (sprintf "in local ~a,\n  ~a" (lname (car loc)) (rec (cdr loc))))))))
308  (define add-loc cons)
309  (define (fragment x)
310    (let ((x (build-expression-tree x)))
311      (cond ((atom? x) x)
312            ((list? x) 
313             (let ((x1 (if (> (length x) +fragment-max-length+)
314                           (append (take x +fragment-max-length+) '(...))
315                           x)))
316               (map (lambda (x) 
317                      (if (and (list? x) (any pair? x))
318                          '(...)
319                          x))
320                    x1)))
321            (else x))))
322  (define (call-result args e loc x)
323    (define (pname)
324      (sprintf "in procedure call to `~s'" (fragment x)))
325    (d "call-result: ~a (~a)" args loc)
326    (let ((ptype (car args))
327          (nargs (length (cdr args))))
328      (check 
329       `(procedure ,(make-list nargs '*) *)
330       ptype
331       loc "a procedure of type" (pname))
332      (let ((atypes (procedure-argument-types ptype (length (cdr args)))))
333        (d "  argument-types: ~a" atypes)
334        (unless (= (length atypes) nargs)
335          (let ((alen (length atypes)))
336            (report 
337             loc
338             (sprintf "~a argument~a" nargs (multiples nargs))
339             (sprintf "~a argument~a" alen (multiples alen))
340             (pname))))
341        (do ((args (cdr args) (cdr args))
342             (atypes atypes (cdr atypes))
343             (i 1 (add1 i)))
344            ((or (null? args) (null? atypes)))
345          (check (car atypes) (car args) loc (sprintf "argument #~a of type" i) (pname)))
346        (let ((r (procedure-result-types ptype)))
347          (d  "  result-types: ~a" r)
348          r))))
349  (define (procedure-argument-types t n)
350    (cond ((or (memq t '(* procedure)) 
351               (not-pair? t) )
352           (make-list n '*))
353          ((eq? 'procedure (car t))
354           (let loop ((at (if (or (string? (second t)) (symbol? (second t)))
355                              (third t)
356                              (second t)))
357                      (m n))
358             (cond ((null? at) '())
359                   ((eq? '#!rest (car at))
360                    (if (pair? (cdr at))
361                        (make-list m (cadr at))
362                        (make-list m '*)))
363                   (else (cons (car at) (loop (cdr at) (sub1 m)))))))
364          (else (bomb "not a procedure type: ~a" t))))
365  (define (procedure-result-types t)
366    (cond ((or (memq t '(* procedure)) 
367               (not-pair? t) )
368           '*)
369          ((eq? 'procedure (car t))
370           (call/cc
371            (lambda (return)
372              (let loop ((rt (if (or (string? (second t)) (symbol? (second t)))
373                                 (cdddr t)
374                                 (cddr t))))
375                (cond ((null? rt) '())
376                      ((eq? '* rt) (return '*))
377                      (else (cons (car rt) (loop (cdr rt)))))))))
378          (else (bomb "not a procedure type: ~a" t))))
379  (define (walk n e loc dest)           ; returns result specifier
380    (let ((subs (node-subexpressions n))
381          (params (node-parameters n)) 
382          (class (node-class n)) )
383      (d "walk: ~a ~a (loc: ~a, dest: ~a)" class params loc dest)
384      (let ((results
385             (case class
386               ((quote) (list (constant-result (first params))))
387               ((##core#undefined) '(undefined))
388               ((##core#proc) '(procedure))
389               ((##core#global-ref) (global-result (first params)))
390               ((##core#variable) (variable-result (first params) e))
391               ((if) (let ((rt (single (walk (first subs) e loc dest) loc)))
392                       (always-true rt loc n)
393                       (let ((r1 (walk (second subs) e loc dest))
394                             (r2 (walk (third subs) e loc dest)))
395                         (cond ((and (not (eq? r1 '*)) (not (eq? '* r2)))
396                                (when (not (= (length r1) (length r2)))
397                                  (report1 
398                                   loc
399                                   "branches in conditional expression differ in the number of results"))
400                                (map (lambda (t1 t2) (simplify `(or ,t1 ,t2)))
401                                     r1 r2))
402                               (else '*)))))
403               ((let)
404                (let ((t (single (walk (first subs) e loc (first params)) loc)))
405                  (walk (second subs) (alist-cons (first params) t e) loc dest)))
406               ((##core#lambda lambda)
407                (decompose-lambda-list
408                 (first params)
409                 (lambda (vars argc rest)
410                   `((procedure
411                      ,@(if dest (list dest) '())
412                      ,(append (make-list argc '*) (if rest '(#!rest) '()))
413                      ,@(let ((r (walk (first subs)
414                                       (if rest
415                                           (alist-cons 
416                                            rest 'list 
417                                            (append (map (lambda (v) (cons v '*)) 
418                                                         (if rest (butlast vars) vars))
419                                                    e))
420                                           e)
421                                       (add-loc dest loc)
422                                       #f)))
423                          (if (eq? r '*)
424                              '(*)
425                              r)))))))
426               ((set!)
427                (let ((rt (single (walk (first subs) e loc (first params)) loc)))
428                  '(undefined)))
429               ((##core#primitive ##core#inline_ref) '*)
430               ((##core#call)
431                (let ((args (map (lambda (n) (single (walk n e loc #f) loc)) subs)))
432                  (call-result args e loc (first subs))))
433               ((##core#switch ##core#cond)
434                (bomb "unexpected node class: ~a" class))
435               (else
436                (for-each (lambda (n) (walk n e loc #f)) subs)
437                '*))))
438        (d "  -> ~a" results)
439        results)))
440  (walk (first (node-subexpressions node)) '() '() #f))
441
442(define (load-type-database name)
443  (and-let* ((rp (repository-path))
444             (dbfile (file-exists? (make-pathname rp name))))
445    (when verbose-mode
446      (printf "loading type database ~a ...~%" dbfile))
447    (for-each
448     (lambda (e)
449       (##sys#put! (car e) '##core#type (cadr e)))
450     (read-file dbfile))))
Note: See TracBrowser for help on using the repository browser.