[m-dev.] Improving mode analysis

Ralph Becket rafe at csse.unimelb.edu.au
Tue Jan 22 17:18:51 AEDT 2008

Mark and I have been discussing improving mode analysis.

The current mode analyser/code scheduler is a fairly scary piece of
work, largely due to the structure it uses to decide when goals can be
scheduled.  I'd like to propose a partial rewrite that reuses as much
of the existing code base as possible, but replace the "delayed goal"
code with the constraint directed mode analysis algorithm implemented a
few summers ago by Richard Fothergill.

The new scheme would work roughly as follows:

(1) The constraint set is constructed for the procedure body (i.e., with
boolean solver variables specifying for each goal whether it produces or
consumes the corresponding program variable).

(2) The scheduler works by using the same greedy scheme as we currently
use, namely iteratively scheduling next the "earliest" (in source-code
order) unscheduled goal for which all input variables have been
constructed.  Information concerning variable construction state is
updated in the constraint store as each goal is scheduled.

Step (2) also handles subtyping analysis, generates instmaps, and so
forth, as it does at present.

* Dealing with higher order code.

Higher order code is handled by requiring that the closure variable be
constructed prior to its application.  The inst of the closure is
inferred as part of the subtyping analysis.

* Dealing with impurity.

To simplify the handling of impurity and add an oft requested feature to
the language, we propose to add a new ordered conjunction scope to the
HLDS.  Goals in an ordered conjunction must be scheduled in the order in
which they appear (of course, subsubgoals in an ordinary conjunction
subgoal can be reordered).  This gives us a simple way to handle impure
code by arranging it in ordered conjunction scopes.  [Mark says this
idea is due to Zoltan.]

Anyone see any show stoppers here?

-- Ralph

mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au

More information about the developers mailing list