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

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

types; scrutinizer tests

File size: 18.0 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 real-name
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 source-info->line)
67
68
69(include "tweaks")
70
71
72(define (d fstr . args)
73  (printf "[debug] ~?~%" fstr args))
74
75;(define-syntax d (syntax-rules () ((_ . _) (void))))
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 ... [#!optional VALOPT1 ...] [#!rest [VAL]]) . RESULTS)
86;       | BASIC
87;   BASIC = * | string | symbol | char | number | boolean | list | pair |
88;           procedure | vector | null | eof | undefined | port |
89;           blob | deprecated
90;   RESULTS = *
91;           | (VAL1 ...)
92
93; global symbol properties:
94;
95;   ##core#type           ->  <typespec>
96;   ##core#declared-type  ->  <bool>
97
98(define-constant +fragment-max-length+ 5)
99
100(define (scrutinize node db)
101  (define (constant-result lit)
102    (cond ((string? lit) 'string)
103          ((symbol? lit) 'symbol)
104          ((number? lit) 'number)
105          ((boolean? lit) 'boolean)
106          ((list? lit) 'list)
107          ((pair? lit) 'pair)
108          ((eof-object? lit) 'eof)
109          ((vector? lit) 'vector)
110          ((and (not (##sys#immediate? lit)) ##sys#generic-structure? lit)
111           `(struct ,(##sys#slot lit 0)))
112          ((null? lit) 'null)
113          ((char? lit) 'char)
114          (else '*)))
115  (define (global-result id loc)
116    (cond ((##sys#get id '##core#type) =>
117           (lambda (a) 
118             (cond ((and (get db id 'assigned)
119                         (not (##sys#get id '##core#declared-type)))
120                    (##sys#put! id '##core#type #f)
121                    '*)
122                   ((eq? a 'deprecated)
123                    (report1 
124                     loc
125                     (sprintf "use of deprecated toplevel identifier `~a'" id) )
126                    '*)
127                   (else (list a)))))
128          (else '*)))
129  (define (variable-result id e loc)
130    (cond ((and (get db id 'assigned) 
131                (not (##sys#get id '##core#declared-type)) )
132           '*)
133          ((assq id e) =>
134           (lambda (a)
135             (when (eq? 'undefined (cdr a))
136               (report1 
137                loc
138                (sprintf "access to variable `~a' which has an undefined value"
139                         (real-name id db))))
140             (list (cdr a))))
141          (else (global-result id loc))))
142  (define (always-true t loc x)
143    (let ((f (cond ((and (pair? t) (eq? 'or (car t)))
144                    (every (cut always-true <> loc x) (cdr t)))
145                   ((memq t '(* boolean undefined)) #f)
146                   (else #t))))
147      (when f
148        (report 
149         loc "of type boolean" 
150         (sprintf 
151          "a result that is of type `~a' and thus always true"
152          t)
153         "value"
154         (sprintf "in conditional `~s'," (fragment x))))
155      f))
156  (define (typename t)
157    (case t
158      ((*) "anything")
159      ((char) "character")
160      (else
161       (cond ((symbol? t) (symbol->string t))
162             ((pair? t)
163              (case (car t)
164                ((procedure) 
165                 (if (or (string? (cadr t)) (symbol? (cadr t)))
166                     (->string (cadr t))
167                     (sprintf "a procedure with ~a returning ~a"
168                              (argument-string (cadr t))
169                              (result-string (cddr t)))))
170                ((or)
171                 (string-intersperse
172                  (map typename (cdr t))
173                  " OR "))
174                ((struct)
175                 (sprintf "a structure of type ~a" (cadr t)))
176                (else (bomb "invalid type: ~a" t))))
177             (else (bomb "invalid type: ~a" t))))))
178  (define (argument-string args)
179    (let ((len (length args))
180          (m (multiples len)))
181      (if (zero? len)
182          "zero arguments"
183          (sprintf 
184           "~a argument~a of type~a ~a"
185           len m m
186           (map typename args)))))
187  (define (result-string results)
188    (if (eq? '* results) 
189        "an unknown number of values"
190        (let ((len (length results))
191              (m (multiples len)))
192          (if (zero? len)
193              "zero values"
194              (sprintf 
195               "~a value~a of type~a ~a"
196               len m m
197               (map typename results))))))
198  (define (simplify t)
199    (let ((t2 (simplify1 t)))
200      (d "simplify: ~a -> ~a" t t2)
201      t2))
202  (define (simplify1 t)
203    (call/cc
204     (lambda (return)
205       (if (pair? t)
206           (case (car t)
207             ((or)
208              (if (= 2 (length t))
209                  (simplify (second t))
210                  (let* ((ts (append-map
211                              (lambda (t)
212                                (let ((t (simplify t)))
213                                  (if (and (pair? t) (eq? 'or (car t)))
214                                      (cdr t)
215                                      (list t))))
216                              (cdr t)))
217                         (ts2 (let loop ((ts ts))
218                                (cond ((null? ts) '())
219                                      ((eq? '* (car ts)) (return '*))
220                                      ((any (cut match (car ts) <>) (cdr ts)) ;XXX broken for subtype-relationship
221                                       (loop (cdr ts)))
222                                      (else (cons (car ts) (loop (cdr ts))))))))
223                    (cond ((equal? ts2 (cdr t)) t)
224                          (else
225                           (d "  or-simplify: ~a" ts2)
226                           (simplify `(or ,@(if (any (cut eq? <> '*) ts2) '(*) ts2))))))))
227             ((procedure)
228              (let ((name (and (not (list? (cadr t))) (cadr t))))
229                `(procedure 
230                  ,@(if name (list name) '())
231                  ,(map simplify (second t))
232                  ,@(map simplify (cddr t)))))
233             (else t))
234           t))))
235  (define (match t1 t2)
236    (let ((m (match1 t1 t2)))
237      (d "match ~a <-> ~a -> ~a" t1 t2 m)
238      m))
239  (define (match1 t1 t2)
240    (cond ((eq? t1 t2))
241          ((eq? t1 '*))
242          ((eq? t2 '*))
243          ((eq? 'procedure t1) (and (pair? t2) (eq? 'procedure (car t2))))
244          ((eq? 'procedure t2) (and (pair? t1) (eq? 'procedure (car t1))))
245          ((memq t1 '(pair list)) (memq t2 '(pair list)))
246          ((memq t1 '(null list)) (memq t2 '(null list)))
247          (else
248           (and (pair? t1) (pair? t2)
249                (cond ((and (eq? (car t1) 'or) (any (cut match <> t2))))
250                      ((and (eq? (car t2) 'or) (any (cut match <> t2))))
251                      (else
252                       (or (eq? (car t1) (car t2))
253                           (and (eq? 'procedure (car t1))
254                                (let ((args1 (if (pair? (second t1)) (second t1) (third t1)))
255                                      (args2 (if (pair? (second t2)) (second t2) (third t2))) 
256                                      (results1 (if (pair? (second t2)) (cdddr t2) (cddr t2))) 
257                                      (results2 (if (pair? (second t2)) (cdddr t2) (cddr t2))) )
258                                  (and (match-args args1 args2)
259                                       (= (length results1) (length results2))
260                                       (every match results1 results2))))
261                           (and (eq? 'struct (car t1))
262                                (equal? t1 t2)))))))))
263  (define (match-args args1 args2)
264    (d "match-args: ~s <-> ~s" args1 args2)
265    (define (match-rest rtype args opt) ;XXX currently ignores `opt'
266      (let-values (((head tail) (break (cut eq? '#!rest <>) args)))
267        (and (every (cut match rtype <>) head) ; match required args
268             (match
269                 rtype
270               (if (and (pair? tail) (pair? (cdr tail)))
271                   (cadr tail)
272                   '*) ) ) ) )
273    (define (optargs a)
274      (memq a '(#!rest #!optional)))
275    (let loop ((args1 args1) (args2 args2) (opt1 #f) (opt2 #f))
276      (cond ((null? args1) 
277             (or opt2
278                 (null? args2)
279                 (optargs (car args2))))
280            ((null? args2) (or opt1 (optargs (car args2))))
281            ((eq? '#!optional (car args1))
282             (loop (cdr args1) args2 #t opt2))
283            ((eq? '#!optional (car args2))
284             (loop args1 (cdr args2) opt1 #t))
285            ((eq? '#!rest (car args1))
286             (match-rest (if (pair? (cdr args1)) (cadr args1) '*) args2 opt2))
287            ((eq? '#!rest (car args2))
288             (match-rest (if (pair? (cdr args2)) (cadr args2) '*) args1 opt1))
289            ((match (car args1) (car args2)) (loop (cdr args1) (cdr args2) opt1 opt2))
290            (else #f))))
291  (define (check expected given loc what #!optional desc) 
292    (d "check: ~a <-> ~a (~a)" expected given loc)
293    (if (match expected given)
294        given
295        (report loc expected given what desc)))
296  (define (multiples n)
297    (if (= n 1) "" "s"))
298  (define (single tv loc)
299    (if (eq? '* tv)
300        '*
301        (let ((n (length tv)))
302          (cond ((= 1 n) (car tv))
303                ((zero? n)
304                 (report loc "a single result" "zero results" #f)
305                 'undefined)
306                (else
307                 (report loc "a single result" (sprintf "~a result~a" n (multiples n)) #f)
308                 (first tv))))))
309  (define (report1 loc desc)
310    (compiler-warning
311     'scrutiny
312     "~a~a" 
313     (location-name loc) desc))
314  (define (report loc expected given what #!optional desc)
315    (report1 
316     loc 
317     (sprintf 
318      "~a~a~a~a"
319      (or desc "")
320      (if desc " " "")
321      (if expected
322          (sprintf "expected ~a~a~a" (or what "") (if what " " "") expected)
323          "")
324      (sprintf ", but where given ~a" given))))
325  (define (location-name loc)
326    (define (lname loc1)
327      (if loc1
328          (sprintf "procedure `~a'" (real-name loc1))
329          "unknown procedure"))
330    (cond ((null? loc) "at toplevel:\n  ")
331          ((null? (cdr loc))
332           (sprintf "in toplevel ~a:\n  " (lname (car loc))))
333          (else
334           (let rec ((loc loc))
335             (if (null? (cdr loc))
336                 (location-name loc)
337                 (sprintf "in local ~a,\n  ~a" (lname (car loc)) (rec (cdr loc))))))))
338  (define add-loc cons)
339  (define (fragment x)
340    (let ((x (build-expression-tree x)))
341      (cond ((atom? x) x)
342            ((list? x) 
343             (let ((x1 (if (> (length x) +fragment-max-length+)
344                           (append (take x +fragment-max-length+) '(...))
345                           x)))
346               (map (lambda (x) 
347                      (if (and (list? x) (any pair? x))
348                          '(...)
349                          x))
350                    x1)))
351            (else x))))
352  (define (call-result args e loc x params)
353    (define (pname)
354      (sprintf 
355       "in procedure call to `~s'~a" 
356       (fragment x)
357       (if (and (pair? params) (pair? (cdr params)))
358           (sprintf " (line ~a)" (source-info->line (cadr params)))
359           "")))
360    (d "call-result: ~a (~a)" args loc)
361    (let ((ptype (car args))
362          (nargs (length (cdr args))))
363      (check 
364       `(procedure ,(make-list nargs '*) *)
365       ptype
366       loc "a procedure of type" (pname))
367      (let ((atypes (procedure-argument-types ptype (length (cdr args)))))
368        (d "  argument-types: ~a" atypes)
369        (unless (= (length atypes) nargs)
370          (let ((alen (length atypes)))
371            (report 
372             loc
373             (sprintf "~a argument~a" alen (multiples alen))
374             (sprintf "~a argument~a" nargs (multiples nargs))
375             (pname))))
376        (do ((args (cdr args) (cdr args))
377             (atypes atypes (cdr atypes))
378             (i 1 (add1 i)))
379            ((or (null? args) (null? atypes)))
380          (check (car atypes) (car args) loc (sprintf "argument #~a of type" i) (pname)))
381        (let ((r (procedure-result-types ptype)))
382          (d  "  result-types: ~a" r)
383          r))))
384  (define (procedure-argument-types t n)
385    (cond ((or (memq t '(* procedure)) 
386               (not-pair? t) )
387           (make-list n '*))
388          ((eq? 'procedure (car t))
389           (let loop ((at (if (or (string? (second t)) (symbol? (second t)))
390                              (third t)
391                              (second t)))
392                      (m n)
393                      (opt #f))
394             (cond ((null? at) '())
395                   ((eq? '#!optional (car at)) 
396                    (loop (cdr at) m #t) )
397                   ((eq? '#!rest (car at))
398                    (if (pair? (cdr at))
399                        (make-list m (cadr at))
400                        (make-list m '*)))
401                   ((and opt (<= m 0)) '())
402                   (else (cons (car at) (loop (cdr at) (sub1 m) opt))))))
403          (else (bomb "not a procedure type: ~a" t))))
404  (define (procedure-result-types t)
405    (cond ((or (memq t '(* procedure)) 
406               (not-pair? t) )
407           '*)
408          ((eq? 'procedure (car t))
409           (call/cc
410            (lambda (return)
411              (let loop ((rt (if (or (string? (second t)) (symbol? (second t)))
412                                 (cdddr t)
413                                 (cddr t))))
414                (cond ((null? rt) '())
415                      ((eq? '* rt) (return '*))
416                      (else (cons (car rt) (loop (cdr rt)))))))))
417          (else (bomb "not a procedure type: ~a" t))))
418  (define (walk n e loc dest)           ; returns result specifier
419    (let ((subs (node-subexpressions n))
420          (params (node-parameters n)) 
421          (class (node-class n)) )
422      (d "walk: ~a ~a (loc: ~a, dest: ~a)" class params loc dest)
423      (let ((results
424             (case class
425               ((quote) (list (constant-result (first params))))
426               ((##core#undefined) '(undefined))
427               ((##core#proc) '(procedure))
428               ((##core#global-ref) (global-result (first params) loc))
429               ((##core#variable) (variable-result (first params) e loc))
430               ((if) (let ((rt (single (walk (first subs) e loc dest) loc)))
431                       (always-true rt loc n)
432                       (let ((r1 (walk (second subs) e loc dest))
433                             (r2 (walk (third subs) e loc dest)))
434                         (cond ((and (not (eq? r1 '*)) (not (eq? '* r2)))
435                                (when (not (= (length r1) (length r2)))
436                                  (report1 
437                                   loc
438                                   "branches in conditional expression differ in the number of results"))
439                                (map (lambda (t1 t2) (simplify `(or ,t1 ,t2)))
440                                     r1 r2))
441                               (else '*)))))
442               ((let)
443                (let loop ((vars params) (body subs) (e2 '()))
444                  (if (null? vars)
445                      (walk (car body) (append e2 e) loc dest)
446                      (let ((t (single (walk (car body) e loc (car vars)) loc)))
447                        (loop (cdr vars) (cdr body) (alist-cons (car vars) t e2))))))
448               ((##core#lambda lambda)
449                (decompose-lambda-list
450                 (first params)
451                 (lambda (vars argc rest)
452                   `((procedure
453                      ,@(if dest (list dest) '())
454                      ,(append (make-list argc '*) (if rest '(#!rest) '()))
455                      ,@(let ((r (walk (first subs)
456                                       (if rest
457                                           (alist-cons 
458                                            rest 'list 
459                                            (append (map (lambda (v) (cons v '*)) 
460                                                         (if rest (butlast vars) vars))
461                                                    e))
462                                           e)
463                                       (add-loc dest loc)
464                                       #f)))
465                          (if (eq? r '*)
466                              '(*)
467                              r)))))))
468               ((set!)
469                (let ((rt (single (walk (first subs) e loc (first params)) loc)))
470                  '(undefined)))
471               ((##core#primitive ##core#inline_ref) '*)
472               ((##core#call)
473                (let ((args (map (lambda (n) (single (walk n e loc #f) loc)) subs)))
474                  (call-result args e loc (first subs) params)))
475               ((##core#switch ##core#cond)
476                (bomb "unexpected node class: ~a" class))
477               (else
478                (for-each (lambda (n) (walk n e loc #f)) subs)
479                '*))))
480        (d "  -> ~a" results)
481        results)))
482  (walk (first (node-subexpressions node)) '() '() #f))
483
484(define (load-type-database name)
485  (and-let* ((rp (repository-path))
486             (dbfile (file-exists? (make-pathname rp name))))
487    (when verbose-mode
488      (printf "loading type database ~a ...~%" dbfile))
489    (for-each
490     (lambda (e)
491       (##sys#put! (car e) '##core#type (cadr e)))
492     (read-file dbfile))))
493
494(define (source-info->line info)
495  (if (list? info)
496      (cadr info)
497      (and info (->string info))) )
Note: See TracBrowser for help on using the repository browser.