[m-dev.] Associating information with HLDS goals.

Paul Bone pbone at csse.unimelb.edu.au
Wed Dec 26 14:39:47 AEDT 2007

Hi Everyone.

I've found that I'd like to associate some extra information with  
HLDS goals.  This information is only needed locally in  
deep_profining.m.  This information describes weather a particular  
goal is trivial, and if a port count is available at some point  
within or before that goal such that after runtime it can be  
determined how often execution reaches the end of that goal.

I'm writing a code transformation that works backwards through HLDS  
goal structures, and from inside to out.  That is, if it considers a  
conjunction, first it will consider the conjunction as a whole, then  
each conjunct in reverse order.  This is because information from  
goals after the current goal is used in the decision of whether a  
coverage point should be inserted after the current goal.

However useful information can also be determined from goals before  
the current goal, I believe the easiest way to handle this is to walk  
over the HLDS first, in normal order and generate some information  
and associate it with each goal.  Then a second pass in reverse can  
gather information that can be gathered when walking over the HLDS in  
reverse order, it will also apply the transformation.

I could use a map to map each goal to the information associated with  
it as found by the first pass, and look up this map for each goal in  
the second pass.  I believe this would run in O(N log N) time.  Using  
an N-ary tree - A tree where each node may have any number of sub- 
trees - I believe I can turn this into linear time.  However it's  
quite messy, because I have to check that the nary tree has the same  
number of branches as there are sub goals of any goal and throw an  
exception otherwise in order to keep my code deterministic.

What I would really like is a structure that mimics the hlds_goal and  
hlds_goal_expr structures, where the hlds_goal function symbol takes  
an extra argument of arbitrary type T.  This would be useful for me,  
and will make my code more simple.  I believe this will likely also  
be useful for others.  But I'm wondering if this is the best option  
of if other similar problems have been solved differently, or in  
which module I should add this data structure.

Any Advice?

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