[mercury-users] .opt files

[Fergus Henderson]

Ralph Becket wrote:
> Looking at array.opt (which I presume is basically for
> inlining optimisations) I see that various procedures including
> array__lookup/3 exist there, but not array__set/4.  While
> array__lookup/3 will be much more heavily used in the Mercury
> implementation of 129.compress, having array__set/4 inlined would also
> be a big help.

Yes, indeed.  Thanks for pointing out this performance bug.

> My first question is, what criteria are used to decide which
> procedures end up in the .opt file?  In the case of array__set/4, the
> C code is almost identical to that of array__lookup/3.

Procedures which satisfy any of the following criteria end up in
the `.opt' file:

	(a) procedures with "simple" bodies
	(b) procedures with higher-order arguments
	(c) procedures which have a `pragma inline' declaration

The heuristic used for determining which procedures have "simple"
bodies seems to be fairly poor -- procedures with more than three
arguments never qualify.  I'm not sure off-hand what the best
fix is, but a work-around would be to add a `pragma inline'
declaration for array__set.

> If both were
> in the .opt file, a procedure doing nothing more than array lookup's
> and set's stands a good chance of having the indirections through the
> array structure to get at the size and elements members moved outside
> the inner loops.

In Mercury 0.6, Mercury arrays were represented as a C structure containing
a size and a pointer to the elements.  But in versions >= 0.7,
the elements are stored directly in the struct, rather than being
allocated separately, so there is one less level of indirection.
Thus there is no load needed to get the address of the elements. 
(The `array->elements' in the source code compiles to an addition,
not a load.)

Also the load to get the array size can be omitted if you disable
bounds checks (see below).

> My second question is, if the compiler could be encouraged to include
> array__set/4 in the .opt file, is gcc smart enough to elide the
> out-of-range tests (it can be deduced from the code, by a human at any
> rate, that this error cannot occur)?

I doubt it.  But I recently committed the change appended below,
which allows you to disable array bounds checks.

P.S.  To test out these changes to array.m (or any other library
module), it is not necessary to rebuild the Mercury library.
You can just copy the module to the same directory as your test case
and rerun `mmake depend'; then you can hack the library module
to your heart's content ;-)

P.P.S.  Please let us know how you go! 
I think your chances are pretty good.

Index: array.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/library/array.m,v
retrieving revision 1.38
retrieving revision 1.39
diff -u -u -r1.38 -r1.39
--- array.m	1997/09/06 18:23:36	1.38
+++ array.m	1997/11/02 12:30:23	1.39
@@ -11,6 +11,15 @@
 % This module provides dynamically-sized one-dimensional arrays.
 % Array indices start at zero.
 
+% By default, the array__set and array__lookup procedures will check
+% for bounds errors.  But for maximum performance, it is possible to
+% disable the checking by compiling with `--intermodule-optimization'
+% and with the C macro symbol `ML_OMIT_ARRAY_BOUNDS_CHECKS'
+% defined, e.g. by using `MCFLAGS=--intermodule-optimization' and
+% `MGNUCFLAGS=-DML_OMIT_ARRAY_BOUNDS_CHECKS' in your Mmakefile,
+% or by compiling with the command
+% `mmc --intermodule-optimization --cflags -DML_OMIT_ARRAY_BOUNDS_CHECKS'.
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -447,16 +456,20 @@
 :- pragma(c_code, array__lookup(Array::array_ui, Index::in,
 		Item::out), "{
 	MR_ArrayType *array = (MR_ArrayType *)Array;
+#ifndef ML_OMIT_ARRAY_BOUNDS_CHECKS
 	if ((Unsigned) Index >= (Unsigned) array->size) {
 		fatal_error(""array__lookup: array index out of bounds"");
 	}
+#endif
 	Item = array->elements[Index];
 }").
 :- pragma(c_code, array__lookup(Array::in, Index::in, Item::out), "{
 	MR_ArrayType *array = (MR_ArrayType *)Array;
+#ifndef ML_OMIT_ARRAY_BOUNDS_CHECKS
 	if ((Unsigned) Index >= (Unsigned) array->size) {
 		fatal_error(""array__lookup: array index out of bounds"");
 	}
+#endif
 	Item = array->elements[Index];
 }").
 
@@ -465,9 +478,11 @@
 :- pragma(c_code, array__set(Array0::array_di, Index::in,
 		Item::in, Array::array_uo), "{
 	MR_ArrayType *array = (MR_ArrayType *)Array0;
+#ifndef ML_OMIT_ARRAY_BOUNDS_CHECKS
 	if ((Unsigned) Index >= (Unsigned) array->size) {
 		fatal_error(""array__set: array index out of bounds"");
 	}
+#endif
 	array->elements[Index] = Item;	/* destructive update! */
 	Array = Array0;
 }").

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.