[MLton-devel] detecting overflow with the C codegen

Stephen Weeks MLton@mlton.org
Wed, 20 Nov 2002 20:47:21 -0800


I think that it might be worth a try to implement the overflow
checking with if-tests inserted by MLton somewhere in the SSA
simplifier pipeline.

For example, "x + y" would get prefixed by the following

if x >= 0
  then if y < maxInt - x then raise Overflow else ()
else if y < minInt - x then raise Overflow else ()

"x - y" can be handled similarly.  I'm not sure what can be done for 
"x * y" -- suggestions appreciated.

That's only an extra arithop and two tests per add/sub, which may be
a lot better than what we're doing now (procedure call, long longs,
...).

Also, the pass that inserts the tests can do better if one of the
arguments is a constant.  For example, "c + y" where c >= 0 would get
prefixed by

if y < c' then raise Overflow else ()

where c' = maxInt - c.

That would be only one extra test per arithop.  To see how common the
one-constant case is, I compiled all the benchmarks and MLton,
counting the number of Int_{add,sub,mul}Checks remaining at the end of
the SSA simplifier.  Each check was either with 2 variables or had 1
variable and 1 constant.  The results are below.  They show that at
least a significant static percentage of the arithops have one
constant argument.

Thoughts?  Better ways to do the tests?

--------------------------------------------------------------------------------

Int_addCheck

benchmark	      2 vars	   1 var 1 const
---------	 ---------------- ---------------
barnes-hut            9   (47.4%)    10   (52.6%)
boyer                 0      (0%)     0      (0%)
checksum              0    (0.0%)     1  (100.0%)
count-graphs          2   (16.7%)    10   (83.3%)
DLXSimulator         22   (57.9%)    16   (42.1%)
fft                   9   (52.9%)     8   (47.1%)
fib                   1  (100.0%)     0    (0.0%)
hamlet              549   (36.9%)   937   (63.1%)
imp-for               0    (0.0%)     1  (100.0%)
knuth-bendix          7   (46.7%)     8   (53.3%)
lexgen                8   (26.7%)    22   (73.3%)
life                  6   (37.5%)    10   (62.5%)
logic                 0    (0.0%)     5  (100.0%)
mandelbrot            1  (100.0%)     0    (0.0%)
matrix-multiply       1   (25.0%)     3   (75.0%)
md5                   4   (10.8%)    33   (89.2%)
merge                 0    (0.0%)     1  (100.0%)
mlton              1755   (41.7%)  2458   (58.3%)
mlyacc               59   (32.8%)   121   (67.2%)
model-elimination    87   (40.3%)   129   (59.7%)
mpuz                  7   (53.8%)     6   (46.2%)
nucleic               0      (0%)     0      (0%)
peek                  6   (85.7%)     1   (14.3%)
psdes-random          0    (0.0%)     1  (100.0%)
ratio-regions        21   (43.8%)    27   (56.2%)
ray                   9   (69.2%)     4   (30.8%)
raytrace             21   (65.6%)    11   (34.4%)
simple               13   (12.3%)    93   (87.7%)
smith-normal-form    20   (90.9%)     2    (9.1%)
tailfib               1  (100.0%)     0    (0.0%)
tak                   0      (0%)     0      (0%)
tensor               17   (58.6%)    12   (41.4%)
tsp                   3   (42.9%)     4   (57.1%)
tyan                 27   (45.0%)    33   (55.0%)
vector-concat         2  (100.0%)     0    (0.0%)
vector-rev            0      (0%)     0      (0%)
vliw                 37   (66.1%)    19   (33.9%)
wc-input1             8   (88.9%)     1   (11.1%)
wc-scanStream         8   (88.9%)     1   (11.1%)
zebra                 2   (16.7%)    10   (83.3%)
zern                  2   (50.0%)     2   (50.0%)


Int_subCheck

benchmark	      2 vars	   1 var 1 const
---------	 ---------------- ---------------
barnes-hut            0    (0.0%)     2  (100.0%)
boyer                 0    (0.0%)     1  (100.0%)
checksum              0    (0.0%)     1  (100.0%)
count-graphs          3   (30.0%)     7   (70.0%)
DLXSimulator          7   (58.3%)     5   (41.7%)
fft                   3   (42.9%)     4   (57.1%)
fib                   0    (0.0%)     2  (100.0%)
hamlet               12    (9.8%)   110   (90.2%)
imp-for               0      (0%)     0      (0%)
knuth-bendix          0    (0.0%)     5  (100.0%)
lexgen                3   (12.5%)    21   (87.5%)
life                  1   (12.5%)     7   (87.5%)
logic                14   (87.5%)     2   (12.5%)
mandelbrot            0    (0.0%)     1  (100.0%)
matrix-multiply       0    (0.0%)     1  (100.0%)
md5                   0    (0.0%)     3  (100.0%)
merge                 0    (0.0%)     1  (100.0%)
mlton               267   (26.1%)   757   (73.9%)
mlyacc               15   (35.7%)    27   (64.3%)
model-elimination    27   (32.9%)    55   (67.1%)
mpuz                  0    (0.0%)     1  (100.0%)
nucleic               0    (0.0%)     1  (100.0%)
peek                  2   (50.0%)     2   (50.0%)
psdes-random          0    (0.0%)     1  (100.0%)
ratio-regions        25   (67.6%)    12   (32.4%)
ray                   2   (14.3%)    12   (85.7%)
raytrace             10   (45.5%)    12   (54.5%)
simple                7    (4.7%)   142   (95.3%)
smith-normal-form     2   (66.7%)     1   (33.3%)
tailfib               0    (0.0%)     2  (100.0%)
tak                   0    (0.0%)     3  (100.0%)
tensor                2   (10.5%)    17   (89.5%)
tsp                   4   (66.7%)     2   (33.3%)
tyan                  7   (24.1%)    22   (75.9%)
vector-concat         0      (0%)     0      (0%)
vector-rev            2  (100.0%)     0    (0.0%)
vliw                 11   (22.4%)    38   (77.6%)
wc-input1             2   (66.7%)     1   (33.3%)
wc-scanStream         2   (66.7%)     1   (33.3%)
zebra                 0    (0.0%)    91  (100.0%)
zern                  0    (0.0%)     4  (100.0%)


Int_mulCheck

benchmark	      2 vars	   1 var 1 const
---------	 ---------------- ---------------
barnes-hut            0      (0%)     0      (0%)
boyer                 0      (0%)     0      (0%)
checksum              0    (0.0%)     1  (100.0%)
count-graphs          0    (0.0%)     4  (100.0%)
DLXSimulator          0    (0.0%)     4  (100.0%)
fft                   0    (0.0%)     6  (100.0%)
fib                   0      (0%)     0      (0%)
hamlet                1   (12.5%)     7   (87.5%)
imp-for               0      (0%)     0      (0%)
knuth-bendix          0      (0%)     0      (0%)
lexgen                2   (28.6%)     5   (71.4%)
life                  0      (0%)     0      (0%)
logic                 0      (0%)     0      (0%)
mandelbrot            0      (0%)     0      (0%)
matrix-multiply       0      (0%)     0      (0%)
md5                   0    (0.0%)    16  (100.0%)
merge                 0    (0.0%)     2  (100.0%)
mlton                21   (15.7%)   113   (84.3%)
mlyacc                0    (0.0%)     7  (100.0%)
model-elimination     0    (0.0%)     6  (100.0%)
mpuz                  3   (33.3%)     6   (66.7%)
nucleic               0      (0%)     0      (0%)
peek                  0      (0%)     0      (0%)
psdes-random          0      (0%)     0      (0%)
ratio-regions         8   (88.9%)     1   (11.1%)
ray                   0    (0.0%)     3  (100.0%)
raytrace              4   (22.2%)    14   (77.8%)
simple                4   (33.3%)     8   (66.7%)
smith-normal-form     0    (0.0%)     8  (100.0%)
tailfib               0      (0%)     0      (0%)
tak                   0      (0%)     0      (0%)
tensor               17   (85.0%)     3   (15.0%)
tsp                   4   (50.0%)     4   (50.0%)
tyan                  8   (88.9%)     1   (11.1%)
vector-concat         0      (0%)     0      (0%)
vector-rev            0      (0%)     0      (0%)
vliw                  1    (4.5%)    21   (95.5%)
wc-input1             0      (0%)     0      (0%)
wc-scanStream         0      (0%)     0      (0%)
zebra                 0      (0%)     0      (0%)
zern                  0    (0.0%)     1  (100.0%)


-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel