[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