[m-dev.] for review: MLDS switch simplification

[Peter Ross]

On Sat, Nov 18, 2000 at 12:36:00AM +1100, Fergus Henderson wrote:
> Estimated hours taken: 12
> 
> Add an MLDS to MLDS transformation that converts MLDS switches
> into computed gotos or if-then-else chains.  (Eventually we
> should make this code also handle binary searches.)
> 
> This transformation should allow tag switch optimization to work for
> the IL back-end.  It also replaces ml_dense_switch.m and lets us
> simplify ml_string_switch.m.
> 
> compiler/mlds.m:
> 	Add a new `switch_range' field to the `switch' stmt.
> 
> compiler/ml_simplify_switch.m:
> 	The new transformation.  This converts MLDS switches into
> 	computed gotos or if-then-else chains.
> 	It uses the new `switch_range' field to determine how big
> 	it would need to make the jump table to cover all cases.
> 
> compiler/ml_switch_gen.m:
> compiler/ml_string_switch.m:
> compiler/ml_tag_switch.m:
> compiler/ml_dense_switch.m:
> 	Generate the new field.
> 	Change the places that generate switches so that after
> 	generating the switch they invoke the new transformation.
> 	Delete ml_dense_switch.m, since it is now redundant,
> 	and significantly simplify ml_string_switch.m.
> 
> compiler/ml_elim_nested.m:
> compiler/ml_optimize.m:
> compiler/ml_tailcall.m:
> compiler/ml_util.m:
> compiler/mlds_to_c.m:
> compiler/mlds_to_il.m:
> 	Trivial changes to handle the new field.
> 
> compiler/switch_util.m:
> compiler/dense_switch.m:
> 	Move most of the code from the `type_range' procedure from
> 	dense_switch.m to switch_util.m, so we can use it in
> 	ml_switch_gen.m for computing the switch range.
> 

Apart from the two minor issues this change looks fine.


> Workspace: /home/pgrad/fjh/ws/hg
> Index: compiler/ml_simplify_switch.m
> ===================================================================
> RCS file: ml_simplify_switch.m
> diff -N ml_simplify_switch.m
> --- /dev/null	Thu Mar 30 14:06:13 2000
> +++ ml_simplify_switch.m	Sat Nov 18 00:02:08 2000

> +
> +:- pred maybe_eliminate_default(mlds__switch_range::in,
> +		list(mlds__switch_case)::in, mlds__switch_default::in, int::in,
> +		int::out, int::out, bool::out) is det.
> +
> +maybe_eliminate_default(Range, Cases, Default, ReqDensity,
> +		FirstVal, LastVal, NeedRangeCheck) :-
> +	% For switches with a default, we normally need to check that
> +	% the variable is in range before we index into the jump table.
> +	% However, if the range of the type is sufficiently small,
> +	% we can make the jump table large enough to hold all
> +	% of the values for the type.

I would prefer this documentation to go above the pred declaration.

> +	(
> +		Default \= default_is_unreachable,
> +		Range = range(Min, Max),
> +		TypeRange = Max - Min + 1,
> +		NumCases = list__length(Cases),
> +		NoDefaultDensity = calc_density(NumCases, TypeRange),
> +		NoDefaultDensity > ReqDensity
> +	->
> +		NeedRangeCheck = no,
> +		FirstVal = Min,
> +		LastVal = Max
> +	;
> +		( Default = default_is_unreachable ->
> +			NeedRangeCheck = no
> +		;
> +			NeedRangeCheck = yes
> +		),
> +		find_first_and_last_case(Cases, FirstCaseVal, LastCaseVal),
> +		FirstVal = FirstCaseVal,
> +		LastVal = LastCaseVal
> +	).
> +

> +
> +	% Generate an rval which will be true iff any of the specified
> +	% list of case conditions matches the specified rval.
> +:- func ml_gen_case_match_conds(mlds__case_match_conds, rval) = rval.
> +ml_gen_case_match_conds([], _) = const(false).
> +ml_gen_case_match_conds([Cond], SwitchRval) =
> +	ml_gen_case_match_cond(Cond, SwitchRval).
> +ml_gen_case_match_conds([Cond1, Cond2 | Conds], SwitchRval) =
> +	binop(or,
> +		ml_gen_case_match_cond(Cond1, SwitchRval),
> +		ml_gen_case_match_conds([Cond2 | Conds], SwitchRval)).
> +
> +	% Generate an rval which will be true iff the specified
> +	% case condition matches the specified rval.
> +:- func ml_gen_case_match_cond(mlds__case_match_cond, rval) = rval.
> +ml_gen_case_match_cond(match_value(CaseRval), SwitchRval) =
> +	% XXX is `eq' the right operator to use here?

I don't understand this XXX.
What other operator could you be using?

> +	binop(eq, CaseRval, SwitchRval).
> +ml_gen_case_match_cond(match_range(MinRval, MaxRval), SwitchRval) =
> +	binop(and, binop(>=, SwitchRval, MinRval),
> +		   binop(<=, SwitchRval, MaxRval)).
> +
> +%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------