[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Gcl-devel] Re: more wild speculation

From: Camm Maguire
Subject: [Gcl-devel] Re: more wild speculation
Date: 18 Jul 2006 11:29:49 -0400
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2


OK, as you probably already know, some support for this is in.  The
algorithm is still too slow -- am working on this.

The basic problem is as follows:

1) r is compiled, r-wl is unknown -- two choices exist for its assumed
   return value when compiling r, '* and nil.  If the latter, r could
   be miscompiled for a while (until later recompiled), as in the
   example (defun r (x) (cond (x 4) ((r-wl x)))) -- this should never
   return fixnum if r-wl is unknown.  So to avoid releasing a possibly
   miscompiled function into the wild, the compiler assumes '* for
   r-wl.  This is different from the case of self-recursion, where one
   can complete the type iteration before releasing the finished
   compiled function.

2) r-wl is compiled, '* is known for 'r, to '* is confirmed for 'r-wl.

3) Neither function is placed on the recompilation table, as neither
   is compiled assuming a signature which has later changed.

To fix this, we have discussed two broad options.  Both require a
special pass looking for function groups calling each other and
returning '*.  One idea is to place such functions in a super state
function, and compile the members as wrappers -- this will maximize
tail recursive and other such optimizations.  The other is to set all
return types in the group to nil and iterate until done.  Either
appears doable.  The real trick is getting the function groups right.
Any such method should get the example in takr.cl right.

Here is what we have right now -- 

Right before the do-recompile step, a pass is made over the hash table
looking for functions with an intersection in their recursive callers
and recursive callees.  This set is restricted to those functions with
at most the &optional keyword in the lambda list source.  A new symbol
is interned, and a new function created which is a state function for
this set -- maximal types for the arguments are computed from those
pertaining to the set members.  The set members are redefined as
wrappers to this state function, and the symbol is placed on their
plist with the 'state-function property.  The set members are placed on
the latter symbol's plist with the 'mutual-recursion-group property.
Finally, the new symbol is added to the callee list of the set
members, and to the recompile list, which then triggers a recompile of
the members.

When any member is defined outside of this process, the state function
is undone, and all members revert to their previous source.  Right
now, they will be left interpreted -- the should likely also go on the
recompile list.

At present, only functions returning '* are considered for this
treatment, but in principle it could be used to accelerate mutual
recursion in other instances.  

I've added a few utilities to help track down '* returns, and have
fixed most in the 'si and 'compiler packages.  These are:

(in-package 'si)
(sig 'foo)
(callees 'foo)
(callers 'foo)
(*s 'compiler) ; all functions returning '* in this package

(old-src 'state-function-symbol) -> '(member-symbols-list member-src-list)

Working on a function with will identify the cause of a '* by
examining all return positions.  Right now, (mapcar 'sig (callees
'foo)) is helpful in this regard.

The killer '*-return-causing combo is frequently something like
(defun foo (x) (cond (x (funcall (get x 'bar))) ((apply (get x 'foo)))))

When funcall or apply are provided known constant symbols or
functions, their return type is propagated, but this is impossible
with unknown functions like these.  I need to look and see how the
older sys-proclaims got so many T returns where we still apparently
get '*. 

Take care,

Robert Boyer <address@hidden> writes:

> I'm puzzled that your wonderful new proclaiming compiler does not see that
> these two functions each return exactly one value.  Why isn't it the case
> that when r-wl is compiled, it is recognized that (a) r needs recompiling
> and that (b) consequently r-wl needs recompiling, and that consequently
> some sort of mutual recursion analysis is called for.
> (defun r (term)
>   (cond ((atom term) term)
>       (t (r-wl 1 2))))
> (defun r-wl (term lst)
>   (cond ((null lst) term)
>       (lst (r 3))
>         (t (r-wl term 4))))
> Thanks!
> Bob

Camm Maguire                                            address@hidden
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]