summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndy Wingo <wingo@pobox.com>2020-03-23 14:45:29 +0100
committerAndy Wingo <wingo@pobox.com>2020-03-23 14:46:53 +0100
commita58758e7822bb97f19ad01b8569dfd82710121ef (patch)
treea089313b9c6965f17a0f3142acc7b52abc91bb1c
parent7839dc444b94568579c510737bc358fa6f4470ee (diff)
Fix fixpoint computation in compute-significant-bits
* module/language/cps/specialize-numbers.scm (preserve-eq?): New helper. (sigbits-union): Use the new helper. Fixes bugs.gnu.org/38486. Thanks to Zack Marvel for the bug report and Matt Wette for tracking it down.
-rw-r--r--module/language/cps/specialize-numbers.scm25
1 files changed, 23 insertions, 2 deletions
diff --git a/module/language/cps/specialize-numbers.scm b/module/language/cps/specialize-numbers.scm
index d5587037b..822ef70b5 100644
--- a/module/language/cps/specialize-numbers.scm
+++ b/module/language/cps/specialize-numbers.scm
@@ -1,6 +1,6 @@
;;; Continuation-passing style (CPS) intermediate language (IL)
-;; Copyright (C) 2015, 2016 Free Software Foundation, Inc.
+;; Copyright (C) 2015, 2016, 2020 Free Software Foundation, Inc.
;;;; This library is free software; you can redistribute it and/or
;;;; modify it under the terms of the GNU Lesser General Public
@@ -159,8 +159,29 @@
($continue kunbox-b src
($primcall 'scm->f64 (a)))))))
+;; compute-significant-bits solves a flow equation to compute a
+;; least-fixed-point over the lattice VAR -> BITMASK, where X > Y if
+;; X[VAR] > Y[VAR] for any VAR. Adjoining VAR -> BITMASK to X results
+;; in a distinct value X' (in the sense of eq?) if and only if X' > X.
+;; This property is used in compute-significant-bits to know when to
+;; stop iterating, and is ensured by intmaps, provided that the `meet'
+;; function passed to `intmap-add' and so on also preserves this
+;; property.
+;;
+;; The meet function for adding bits is `sigbits-union'; the first
+;; argument is the existing value, and the second is the bitmask to
+;; adjoin. For fixnums, BITMASK' will indeed be distinct if and only if
+;; bits were added. However for bignums it's possible that (= X' X) but
+;; not (eq? X' X). This preserve-eq? helper does the impedance matching
+;; for bignums, returning the first value if the values are =.
+(define (preserve-eq? x x*)
+ (if (= x x*)
+ x
+ x*))
+
(define (sigbits-union x y)
- (and x y (logior x y)))
+ (and x y
+ (preserve-eq? x (logior x y))))
(define (sigbits-intersect x y)
(cond