[m-dev.] diff: fix switches in IL

[Fergus Henderson]

On 09-Nov-2000, Tyson Dowd <trd at cs.mu.OZ.AU> wrote:
> compiler/mlds_to_il.m:
> 	Implement cast_to_unsigned unop.
...
> @@ -1300,8 +1296,7 @@
>  unaryop_to_il(std_unop(mkbody),	_, comment_node("mkbody (a no-op)")) --> [].
>  unaryop_to_il(std_unop(unmkbody), _, comment_node("unmkbody (a no-op)")) --> [].
>  
> -unaryop_to_il(std_unop(cast_to_unsigned), _,
> -	throw_unimplemented("unimplemented cast_to_unsigned unop")) --> [].
> +unaryop_to_il(std_unop(cast_to_unsigned), _, instr_node(conv(uint32))) --> [].

I'm afraid that won't not be sufficient.
`cast_to_unsigned' is a bit of a hack, unfortunately.
The way we use it is not just to convert a value to unsigned, but
actually to change the semantics of the enclosing operator so that it
is e.g. an unsigned comparison rather than a signed comparison.

For the MLDS back-end, currently it is only used in ml_dense_switch.m,
where we have

                { InRange = binop(<=, unop(std_unop(cast_to_unsigned), Index),
                                const(int_const(Difference))) },

This is adapted from similar code in dense_switch.m for the LLDS back-end.
I didn't notice this issue when I was writing ml_dense_switch.m,
otherwise I probably would have done something different.

On thing we could do is to add additional unsigned operators,
either in the standard builtin_ops__binary_op or perhaps just in the
MLDS.  In particular we need unsigned versions of `<=', `div', and `mod'.

Another approach we could take is just to avoid using cast_to_unsigned.
Unsigned `<=' is used in dense switches and lookup switches.
It's used to do a range check with a single comparison.
For that, there is another alternative: we could output the test as
`Index >= 0 && Index <= Max', i.e.

                { InRange = binop(and,
				binop(>=, Index, const(int_const(0))),
				binop(<=, Index,
					const(int_const(Max))) },

instead of as `((Unsigned) Index) <= Max', and rely on the back-end
optimizing that test into a single comparison.  GNU C does that
optimization, and for other C compilers and other back-ends we could
also do it ourselves in mlds_to_c.m/mlds_to_il.m.

Unsigned `div' and `mod' are used in lookup switches, but that can
easily be avoided by using `>>' and `&' instead -- this would probably
be a good idea for the IL back-end (and the JVM back-end) anyway;
currently we're relying on the C compiler to optimize unsigned
division or modulus by a constant into shift or and, and while
any decent C compiler ought to do that, a JIT compiler might not.

Any comments as to which of these two approaches is preferable?

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------