[m-rev.] for review: specialize all calls to {string, io}.format

[Julien Fischer]

Hi Zoltan,

On Fri, 21 Nov 2014, Zoltan Somogyi wrote:

> I would like the review to look at the following issues in particular,
> each marked by an XXX in the code.
>
> Should we implicitly import string.format.m and string.parse_util.m
> (the two modules needed by the specialization of calls to string.format
> and io.format) in all modules? In all modules that import string.m?
> Or just the modules that may call a format predicate, as in this diff?

I think what you have in this diff is fine.  The only issue, as I understand
it, is that you may unnecessarily implicitly import the above modules into a
module that defines its own predicates or functions named 'format'.  That seems
as though it would be (1) fairly rare and (2) harmless.

> We didn't specialize calls to stream.string_writer.format before
> this diff, and we don't after. I think it should be simple to implement,
> but I don't want to do it without meaningful tests. At the moment,
> the test suite has only one test of that function, and it is trivial.
> Does anyone have any code that could be used as a more substantial test?

As I take it, specialising calls to string_writer.format boils down to:

(1) the "string.format" approach: build up a the string by appending the
substrings generated by each component of the format string and then 'put'
the resulting string to the string writer stream.

(2) the "io.format" approach: build up the substrings corresponding to the
components of the format string and 'put' them individually to the string
writer stream.

I've had a look through the code that I have that uses streams and could not
find anything that would be useful as a test.  Even if such code existed I
don't think it would tell you anything useful anyway.  Code using streams is
almost always intended to be generic in the underlying stream and in the
absence of information about the relative costs of appending strings versus
method calls to 'put' for the _specific_ instance stream in question you cannot
decide between the two alternatives above.

On balance, I think that you should handle calls to string_writer.format as per
(1) above since that approach is not going to be any worse than what we already
do at runtime.  Short of doing lots of type class method specialisation and
inlining or in the absence of, for example, profiling feedback you won't be
able to do better.

> Should we add a nonempty_list type to library/list.m? We already have
> such an inst, and we have the equivalent type one_or_more in the compiler.

I'm not convinced such a type is generally useful enough to be included in the
standard library.  In principle, the non_empty, inst ought to be sufficient.
In practice the current mode checker sometimes makes using it a bit hairy.
(Possibly Peter Wang's recent changes to the mode checker have improved the
situation though.)

> Or should we add a version of maybe_error in which the error alternative
> lists one or more errors?

I have no objection to adding such a type.

> As for whether the compiler should , by default,print more than one
> error message for one call to a format predicate, I think we will need
> to see the second (and maybe later) messages from real, non-test errors
> to see whether they are useful or misleading.

Agreed.

...

> Specialize ALL calls to string.format and io.format.
> 
> Previously, we specialized calls to string.format and io.format only if
> the format string specified no flags, widths, precisions or non-default
> bases for any conversion. We now specialize calls to those predicates
> regardless of the format string. To make this possible, we now have two
> copies of the code to parse format strings.

...


> diff --git a/compiler/format_call.m b/compiler/format_call.m
> index af654c4..d99522a 100644
> --- a/compiler/format_call.m
> +++ b/compiler/format_call.m

...

> @@ -79,23 +80,22 @@
>  % cases is controlled by a separate option, which is consulted in det_report.m.
>  %
>  % We could in theory track e.g. format strings through calls to library
> -% functions such as string.append. However, there is no convenient way to
> -% evaluate the extent of a need for this capability until this change is
> -% bootstrapped, so that is left for future work.
> +% functions such as string.append. However, we have not yet felt the need
> +% for this in practice.
>  %
> -% The second job (optimizing the calls) starts by gathering the information
> -% we need during the first pass through the code. If we find that a format_call
> -% can be executed by string.format on dummy values of the appropriate type
> -% without throwing an exception, we check to see if the format string is simple
> -% enough for us to interpret it at compile time. At the moment, it is simple
> -% enough if it consists of only raw text to be printed and uses of the %d,
> -% %c and %s specifiers without any flags, width or precision specifications
> -% or anything like that. If the format string falls into this category,
> -% then we construct code to replace the call right away.
> +% The second job (optimizing the calls) starts by procesing the information

s/procesing/processing/

> +% gathered by the first pass through the code. For each call site, we
> +% systematically convert each component of the format string and its associated
> +% value to be printed (if any) to a string, and then either append the
> +% resulting strings together (if the original call was to string.format),
> +% or print the resulting strings as they are produced (if the original call
> +% was to io.format). We do not yet optimize calls to the predicate
> +% stream.string_writer.format. For each call site that we could optimize,
> +% we record its replacement in a map.
>  %
>  % If there are any such replacements, we perform a second backward traversal of
> -% the procedure body, looking for the goals to be replaced, which we identity
> -% by goal_id.
> +% the procedure body, looking for the goals to be replaced (which we identity
> +% by goal_id), and replace them.
>  %
>  % For each call we want to optimize, we also want to delete the code that
>  % constructs the format string and the lists of poly_types. The first pass

...

> @@ -201,16 +205,13 @@
>  :- type list_skeleton_map   == map(prog_var, list_skeleton_state).
>
>      % Maps each variable representing a polytype in the list of values to be
> -    % printed to the variable whose value is to be printed, and a dummy value
> -    % of the same kind. We don't include the actual value to be printed, since
> -    % (a) in almost all cases that won't be available statically in the
> -    % program, and (b) we don't actually need it.
> -:- type what_to_print
> -    --->    what_to_print(
> -                var_to_print        :: prog_var,
> -                dummy_to_print      :: string.poly_type
> -            ).
> -:- type list_element_map    == map(prog_var, what_to_print).
> +    % printed to an abtract representation of that polytype, with the

s/abtract/abstract/

> +    % actual value to be printed replaced by the variable that will hold
> +    % that value at runtime.
> +    %
> +    % For example, when we find the unification X = string.poly_type.s(Y),
> +    % we add to the list_element_map an entry mapping X to apt_s(Y).
> +:- type list_element_map    == map(prog_var, abstract_poly_type).
>
>      % Maps each variable defined in terms of another variable to the variable
>      % it is assigned from.

....

> +%-----------------------------------------------------------------------------%
> 
> -:- pred replace_string_format(module_info::in, list(string_component)::in,
> -    maybe(prog_var)::in, prog_var::out, list(hlds_goal)::out,
> +    % For optimizing e.g. io.format(Stream, "%3d_%.5x", [i(X), i(Y)], IO0, IO),
> +    % generate code that looks like this:
> +    %
> +    %   ... set up Flags1 ...
> +    %   Width2 = 3,
> +    %   Base3 = base_hex_lc,
> +    %   format_unsigned_int_component_width_noprec(Flags1, Width2, Base3, X,
> +    %       Str4),
> +    %   io.write_string(Stream, Str4, IO0, IO5),
> +    %   Str5 = "_",
> +    %   io.write_string(Stream, Str5, IO5, IO6),
> +    %   ... set up Flags7 ...
> +    %   Prec8 = 5,
> +    %   format_signed_int_component_nowidth_prec(Flags1, Prec2, Y, Str9),
> +    %   io.write_string(Stream, Str9, IO5, IO),
> +    %
> +    % We convert the components in the original order, and print each string
> +    % resulting from converting a component as soon as it is ready.
> +    % These strings should therefore never need to be stored in stack slots.
> +    %
> +    % If the original call was to io.format/4 instead of io.format/5,
> +    % i.e. if the stream to be printed on was implicit, then the calls
> +    % to io.write_string that we generate will also have the stream to be
> +    % printed on implicit. The runtime system will retrieve the current
> +    % output stream in each of those calls to io.write_string/3. We could
> +    % test to see whether factoring out this hidden repetition would be
> +    % worthwhile.

In C grades retrieving the current output stream involves a function call plus
an access to a thread local mutable (in .par grades).  (I didn't look at what
the non-C grades do but it's presumably something similar).  If optimizing the
retrieval of the implicit stream were worth it then it would be worth doing for
for all conjunctions of "primitive" I/O operations that cannot change the
current output stream, not just the ones introduced by this module.  In short,
it's a separate issue from what this change does.

...

> +
> +    % This predicate generates code of the form
> +    %
> +    %   VarHash  = flag_hash_clear,
> +    %   VarSpace = flag_hash_set,
> +    %   VarZero  = flag_hash_clear,
> +    %   VarMinus = flag_hash_clear,
> +    %   VarPlus  = flag_hash_clear,
> +    %   Flags = string_format_flags(VarHash, VarSpace, VarZero, VarMinus,
> +    %       VarPlus)
> +    %
> +    % While this looke like a lot, it should actually compile down into

s/looke/looks/

> +    % a single machine instruction, due to the packing of enums inside
> +    % structures.
> +    %
> +:- pred build_flags_arg(string_format_flags::in, prog_var::out,
> +    list(hlds_goal)::out,
> +    prog_varset::in, prog_varset::out, vartypes::in, vartypes::out) is det.
> +
> +build_flags_arg(Flags, Var, Goals, !VarSet, !VarTypes) :-
> +    Flags = string_format_flags(FlagHash, FlagSpace, FlagZero, 
> +        FlagMinus, FlagPlus),


...


> diff --git a/compiler/parse_string_format.m b/compiler/parse_string_format.m
> index e69de29..2c56dfe 100644
> --- a/compiler/parse_string_format.m
> +++ b/compiler/parse_string_format.m
> @@ -0,0 +1,575 @@
> +%----------------------------------------------------------------------------%
> +% vim: ts=4 sw=4 et ft=mercury
> +%----------------------------------------------------------------------------%
> +% Copyright (C) 2014 The Mercury team.
> +% This file may only be copied under the terms of the GNU Library General
> +% Public License - see the file COPYING.LIB in the Mercury distribution.
> +%----------------------------------------------------------------------------%

Cut-and-paste error: compiler modules are licensed under the GPL not LGPL.

> +%
> +% File: parse_string_format.m.
> +%
> +% This module parses format strings for the compiler; the module
> +% library/string.parse_runtime.m does the same job for the runtime system.
> +% Any changes here, in the parts of this module below the code of
> +% flatten_components, will probably also require a corresponding change there.
> +%
> +%----------------------------------------------------------------------------%
> +%----------------------------------------------------------------------------%
> +
> +:- module check_hlds.simplify.format_call.parse_string_format.
> +:- interface.
> +
> +:- import_module parse_tree.
> +:- import_module parse_tree.prog_data.
> +
> +:- import_module string.parse_util.
> +:- import_module list.
> +:- import_module pair.
> +
> +%----------------------------------------------------------------------------%
> +
> +    % An abtract representation of a polytype, with the actual value
> +    % to be printed replaced by the variable that will hold that value
> +    % at runtime.
> +:- type abstract_poly_type
> +    --->    apt_f(prog_var)
> +    ;       apt_i(prog_var)
> +    ;       apt_s(prog_var)
> +    ;       apt_c(prog_var).
> +
> +:- type compiler_format_maybe_width
> +    --->    compiler_no_specified_width
> +    ;       compiler_manifest_width(int)
> +    ;       compiler_var_width(prog_var).
> +
> +:- type compiler_format_maybe_prec
> +    --->    compiler_no_specified_prec
> +    ;       compiler_manifest_prec(int)
> +    ;       compiler_var_prec(prog_var).
> +
> +:- type flat_component
> +    --->    flat_string_const(string)
> +    ;       flat_format_char(
> +                string_format_flags,
> +                compiler_format_maybe_width,
> +                prog_var
> +            )
> +    ;       flat_format_string(
> +                string_format_flags,
> +                compiler_format_maybe_width,
> +                compiler_format_maybe_prec,
> +                prog_var
> +            )
> +    ;       flat_format_signed_int(
> +                string_format_flags,
> +                compiler_format_maybe_width,
> +                compiler_format_maybe_prec,
> +                prog_var
> +            )
> +    ;       flat_format_unsigned_int(
> +                string_format_flags,
> +                compiler_format_maybe_width,
> +                compiler_format_maybe_prec,
> +                string_format_int_base,
> +                prog_var
> +            )
> +    ;       flat_format_float(
> +                string_format_flags,
> +                compiler_format_maybe_width,
> +                compiler_format_maybe_prec,
> +                string_format_float_kind,
> +                prog_var
> +            ).
> +
> +    % Parse the entire format string. Return either a list of things to be
> +    % formated and printed, or a list of error messages.

s/formated/formatted/

> +    %
> +:- pred parse_and_flatten_format_string(list(char)::in,
> +    list(abstract_poly_type)::in,
> +    maybe_error(list(flat_component),
> +        pair(string_format_error, list(string_format_error)))::out) is det.
> +% XXX Should we introduce a new type, nonempty_list? We already have the inst.
> +

...


> diff --git a/library/Mmakefile b/library/Mmakefile
> index b7ad2a7..931ce73 100644
> --- a/library/Mmakefile
> +++ b/library/Mmakefile
> @@ -170,7 +170,7 @@ endif
>  # targets
>
>  .PHONY: all
> -all:	mercury all-ints $(TAGS_FILE_EXISTS)
> +all:	mercury all-ints $(TAGS_FILE_EXISTS) check_doc_undoc
>
>  .PHONY: mercury
>  mercury: lib_std
> @@ -210,6 +210,21 @@ $(STD_LIB_NAME).trans_opts: $($(STD_LIB_NAME).trans_opts)
>
>  #-----------------------------------------------------------------------------#
> 
> +.PHONY: check_doc_undoc
> +check_doc_undoc: MODULES_DOC MODULES_UNDOC *.m
> +	@{																\
> +		cat MODULES_DOC MODULES_UNDOC | sort > FILES_VIA_MODULES;	\
> +		ls *.m > FILES_VIA_LS;										\
> +		if diff -u FILES_VIA_MODULES FILES_VIA_LS; then				\
> +			true;													\
> +		else														\
> +			false;													\
> +		fi;															\
> +		rm -f FILES_VIA_MODULES FILES_VIA_LS;						\
> +	}
> +

The spacing before the line continuation characters looks awry there.

...

The change looks fine otherwise.

Cheers,
Julien.