[m-rev.] for review: model_non lookup switches

[Julien Fischer]

On Mon, 24 Apr 2006, Zoltan Somogyi wrote:

> Implement lookup switches in which a switch arm may contain more than one
> solution, such as this code here:
>
> 	p(d, "four", f1, 4.4).
> 	p(e, "five", f2, 5.5).
> 	p(e, "five2", f3(5), 55.5).
> 	p(f, "six", f4("hex"), 6.6).
> 	p(g, "seven", f5(77.7), 7.7).
> 	p(g, "seven2", f1, 777.7).
> 	p(g, "seven3", f2, 7777.7).
>
> Such code occurs frequently in benchmark programs used to evaluate the
> performance of tabled logic programming systems.
>
> Change frameopt.m, which previously worked only on det and semidet code,
> to also work for nondet code. For predicates such as the one above, frameopt
> can now arrange for the predicate's nondet stack frame to be created only
> when a switch arm that has more than one solution is selected.
>
> compiler/lookup_switch.m:
> 	Extend the existing code for recognizing and implementing lookup
> 	switches to recognize and implement them even if they are model_non.
>
> compiler/lookup_util.m:
> 	New module containing utility predicates useful for implementing
> 	both lookup switches, and in the future, lookup disjunctions (i.e.
> 	disjunctions that correspond to a nondet arm of a lookup switch).
>
> compiler/ll_backend.m:
> 	Include the new module.

You also need to mention it in compiler/notes/compiler_design.html.

> compiler/global_data.m:
> 	Move the job of filling in dummy slots to our caller, in this case
> 	lookup_switch.m.
>
> compiler/frameopt.m:
> 	Generalize the existing code for delaying stack frame creation,
> 	which worked only on predicates that live on the det stack, to work
> 	also on predicates that live on the nondet stack. Without this,
> 	predicates whose bodies are model_non lookup switches would create
> 	a nonstack stack frame before the switch is ever entered, which
> 	is wasteful if the selected switch arm has at most one solution.
>
> 	Since the structure of model_non predicates is more complex (you can
> 	cause a branch to a label by storing its address in a redoip slot,
> 	you can succeed from the frame without removing the frame), this
> 	required considerable extra work. To make the new code debuggable,
> 	record, for each basic block that needs a stack frame, *why* it
> 	needs that stack frame.
>
> compiler/opt_util.m:
> 	Be more conservative about what refers to the stack. Export some
> 	previously internal functionality for frameopt. Turn some predicates
> 	into functions, and rename them to better reflect their purpose.
>
> compiler/opt_debug.m:
> 	Print much more information about pragma_c and call LLDS instructions.
>
> compiler/prog_data.m:
> 	Add an extra attribute to foreign_procs that says that the code
> 	of the foreign_proc assumes the existence of a stack frame.
> 	This is needed to avoid frameopt optimizing the stack frame away.
>
> compiler/add_pragma.m:
> 	When processing fact tables, we create foreign_procs that assume
> 	the existence of the stack frame, so set the new attribute.
>
> compiler/pragma_c_gen.m:
> 	When processing foreign_procs, transmit the information in the
> 	attribute to the generated LLDS code.
>
> compiler/llds.m:
> 	Rename the function symbols referring to the fixed slots in nondet
> 	stack frames to make them clearer and to avoid overloading function
> 	symbols such as curfr and succip.
>
> 	Rename the function symbols of the call_model type to avoid overloading
> 	the function symbols of the code_model type.
>
> 	Add a new field to the c_procedure type giving the code_model of the
> 	procedure, and give names to all the fields.
>
> 	Describe the stack slots used by lookup switches to the debugger
> 	and native gc.
>
> compiler/options.m:
> doc/user_guide.texi:
> 	Add a new option, --debug-opt-pred-name, that does when the existing
> 	--debug-opt-pred-id options does, but taking a user-friendly predicate
> 	name rather than a pred_id as its argument.
>
> compiler/handle_options.m:
> 	Process --debug-opt-pred-name, and make --frameopt-comments imply
> 	--auto-comments, since it is not useful without it.
>
> 	Reformat some existing comments that were written in the days of
> 	8-space indentation.
>
> compiler/optimize.m:
> 	Implement the new option.
>
> 	Use the new field of the c_procedure type to try only the version
> 	of frameopt appropriate for the code model of the current procedure.
>
> 	Do a peephole pass after frameopt, since frameopt can generate code
> 	sequences that peephole can optimize.
>
> 	Make the mechanism for recording the process of optimizing procedure
> 	bodies more easily usable by including the name of the optimization
> 	that created a given version of the code in the name of the file
> 	that contains that version of the code, and ensuring that all numbers
> 	are two characters long, so that "vi procname*.opt*" looks at the
> 	relevant files in the proper chronological sequence, instead of having
> 	version 11 appear before version 2.
>
> compiler/peephole.m:
> 	Add a new optimization pattern: a "mkframe, goto fail" pair (which
> 	can be generated by frameopt) should be replaced by a simple "goto
> 	redo".
>
> compiler/code_gen.m:
> 	Factor out some common code.
>
> compiler/llds_out.m:
> 	Ensure that C comments nested inside comment(_) LLDS instructions
> 	aren't emitted as nested C comments, since C compilers cannot handle
> 	these.
>
> compiler/code_info.m:
> compiler/code_util.m:
> compiler/continuation_info.m:
> compiler/dupelim.m:
> compiler/exprn_aux.m:
> compiler/jumpopt.m:
> compiler/livemap.m:
> compiler/llds_out.m:
> compiler/mercury_compile.m:
> compiler/middle_rec.m:
> compiler/ml_code_gen.m:
> compiler/opt_debug.m:
> compiler/opt_util.m:
> compiler/peephole.m:
> compiler/stack_layout.m:
> compiler/transform_llds.m:
> compiler/var_locn.m:
> 	Conform to the change to prog_data.m, opt_util.m and/or llds.m.
>
> tests/hard_coded/dense_lookup_switch_non.{m,exp}:
> 	New test case to exercise the new algorithm.
>
> tests/hard_coded/Mmakefile:
> 	Enable the new test case.
>
> tests/hard_coded/cycles.m:
> 	Make this test case conform to our coding convention.

...

> +:- typeclass block_entry_exit(En, Ex) <= ((En -> Ex), (Ex -> En)) where [
> +    pred detect_entry(list(instruction)::in, list(instruction)::out,
> +        list(instruction)::out, En::out) is semidet,
> +    pred detect_exit(list(instruction)::in, En::in, list(instruction)::out,
> +        list(instruction)::out, list(instruction)::out, Ex::out) is semidet,
> +    func late_setup_code(En) = list(instruction),
> +    func non_teardown_exit_code(Ex) = list(instruction),
> +    func describe_entry(En) = string,
> +    func describe_exit(proc_label, Ex) = string
> +].

That appears to be the first use of functional dependencies in the compiler
itself.

...

> @@ -1261,39 +1745,43 @@
>              % that sets up the resumption point saves the address of Label on
>              % the stack, and thus is already known to need a stack frame.
>              Predecessors = [],
> -            svmap.det_update(Label, block_needs_frame, !OrdNeedsFrame)
> +            ord_needs_frame(Label, Reason, !OrdNeedsFrame)
>          ),
>          list.filter(all_successors_need_frame(BlockMap, !.OrdNeedsFrame),
>              Predecessors, NowNeedFrameLabels),
> -        list.foldl2(record_frame_need(BlockMap), NowNeedFrameLabels,
> +        list.foldl2(record_frame_need(BlockMap, Reason), NowNeedFrameLabels,
>              !OrdNeedsFrame, !CanTransform),
> -        svqueue.put_list(NowNeedFrameLabels, !Queue),
> +        % XXX map.lookup(BlockMap, Label, BlockInfo),
> +        % XXX Successors = successors(BlockInfo),
> +        list.map(pair_with(pred_propagated(Label, Reason)), NowNeedFrameLabels,

Why is the commented out code with the XXXs there?

If you haven't already done so then I suggest bootstrapping it with
`--intermodule-optimization' enabled, otherwise that looks fine.

Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------