[m-dev.] for review: use shift and mask in lookup switches

[Fergus Henderson]

Estimated hours taken: 0.75

compiler/lookup_switch.m:
	Use shifts and masks rather than unsigned division and
	unsigned modulus.  There's two reasons for this change.
	The main one is to reduce the number of places where we
	depend on `cast_to_unsigned'.  The other reason is so
	that we generate better code for the IL back-end (and
	for any future back-ends like it, e.g. the JVM back-end).

Workspace: /home/pgrad/fjh/ws/hg
Index: compiler/lookup_switch.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/lookup_switch.m,v
retrieving revision 1.38
diff -u -d -r1.38 lookup_switch.m
--- compiler/lookup_switch.m	2000/09/19 03:05:13	1.38
+++ compiler/lookup_switch.m	2000/11/09 14:16:27
@@ -346,10 +346,9 @@
 	% iff we have a case for that tag value.
 lookup_switch__generate_bitvec_test(Index, CaseVals, Start, _End,
 		CheckCode) -->
-	lookup_switch__get_word_bits(WordBits),
+	lookup_switch__get_word_bits(WordBits, Log2WordBits),
 	generate_bit_vec(CaseVals, Start, WordBits, BitVec),
 
-	{ UIndex = unop(cast_to_unsigned, Index) },
 		%
 		% Optimize the single-word case:
 		% if all the cases fit into a single word, then
@@ -362,32 +361,49 @@
 		BitVec = create(_, [yes(SingleWord)], _, _, _, _, _)
 	->
 		Word = SingleWord,
-		BitNum = UIndex
+		BitNum = Index
 	;
-		WordNum = binop(/, UIndex, const(int_const(WordBits))),
+		% This is the same as
+		% WordNum = binop(/, Index, const(int_const(WordBits)))
+		% except that it can generate more efficient code.
+		WordNum = binop(>>, Index, const(int_const(Log2WordBits))),
+
 		Word = lval(field(yes(0), BitVec, WordNum)),
-		BitNum = binop(mod, UIndex, const(int_const(WordBits)))
+
+		% This is the same as
+		% BitNum = binop(mod, Index, const(int_const(WordBits)))
+		% except that it can generate more efficient code.
+		BitNum = binop(&, Index, const(int_const(WordBits - 1)))
 	},
 	{ HasBit = binop((&),
 			binop((<<), const(int_const(1)), BitNum),
 			Word) },
 	code_info__fail_if_rval_is_false(HasBit, CheckCode).
 
-:- pred lookup_switch__get_word_bits(int::out, code_info::in, code_info::out)
-	is det.
+:- pred lookup_switch__get_word_bits(int::out, int::out,
+	code_info::in, code_info::out) is det.
 
 	% Prevent cross-compilation errors by making sure that
 	% the bitvector uses a number of bits that will fit both
 	% on this machine (so that we can correctly generate it),
 	% and on the target machine (so that it can be executed
-	% correctly)
+	% correctly).  Also make sure that the number of bits that
+	% we use is a power of 2, so that we implement division as
+	% right-shift (see above).
 
-lookup_switch__get_word_bits(WordBits) -->
+lookup_switch__get_word_bits(WordBits, Log2WordBits) -->
 	{ int__bits_per_int(HostWordBits) },
 	code_info__get_globals(Globals),
 	{ globals__get_options(Globals, Options) },
 	{ getopt__lookup_int_option(Options, bits_per_word, TargetWordBits) },
-	{ int__min(HostWordBits, TargetWordBits, WordBits) }.
+	{ int__min(HostWordBits, TargetWordBits, WordBits0) },
+	% round down to the nearest power of 2
+	{ Log2WordBits = log2_rounded_down(WordBits0) },
+	{ int__pow(2, Log2WordBits, WordBits) }.
+
+:- func log2_rounded_down(int) = int.
+log2_rounded_down(X) = Log :-
+	int__log2(X + 1, Log + 1).  % int__log2 rounds up
 
 :- pred generate_bit_vec(case_consts::in, int::in, int::in, rval::out,
 	code_info::in, code_info::out) is det.

-- 
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
--------------------------------------------------------------------------