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

A question about tweaking the 3600 Lisp Compiler

    Date: Fri, 4 Mar 88 11:00 PST
    From: Siskind.pa@Xerox.COM

    I am doing some experiments where I compile SAT problems
    (Boolean satisfiability) and CSP problems (Constraint Satisfaction
    problems) directly into very tight Lisp code. The code is very simple.
    It is not very Lisp-like and ressembles Assembler code. It is all one
    large PROG with lots of IF-EQ-GOTOs and some SETQs to local variables.
    I can generate such code from the SAT/CSP problems quite quickly. The good
    thing about such code is that once it is compiled it runs exceedingly
    quickly (about 10,000 times faster than other more sophisticated SAT/CSP
    solvers which I have tried). The only problem is that the 3600 Lisp compiler
    takes forever to compile the large proceedures which my SAT/CSP-Lisp translater
    generates because of all of the optimization which is being done. 

Are you sure it's the optimization, or is that just an assumption?

								      All of
    that optimization is useless for this application as the code which I
    generate has a trivial one-to-one correspondence to the most optimal
    3600 machine instruction sequences which the compiler ends up prducing.
    I tried setting both COMPILER:*PHASE-1-OPTIMIZE-P* and COMPILER:*RUN-PHASE-3*
    to NIL. That helped a bit but not enough.

    Question 1: How do I turn off ALL optimizations.

I would first use metering tools, even crude ones like pressing c-m-Suspend
a statistically significant number of times while compiling, to find out
where the time is being spent.  Only then should you worry about turning
things off.

You can start by eschewing macros like IF and PUSH, as well as optimizable
functions like LIST, if you're really aware of a one-to-one correspondence
between your code and machine instructions.

    Question 2: I know the machine code sequences which I want to generate.
    There are only two general templates of length 6 and 2 instructions
    respectively. Can I use an assembler directly and I how do I do that?

It's a little known fact, but there is a crude assembler buried somewhere
in the system.  I'd rather not tell you how to use it, for three reasons.
One is that it won't actually work for you; without some modifications, it
won't assemble code that you can call as an ordinary function.  Second is
that if you adopt that approach, your code won't port to future machine
offerings.  Third, because of the way that assembler is implemented, it
may well be slower than the compiler.  We can keep this idea in reserve
in case better ideas don't pan out, but currently I doubt that the assembler
will be the answer to your problems.

    Question 3: Is there an indirect GOTO instruction? If there is, how do I
    access it directly from lisp? 

In 7.2 the CASE construct compiles into an indexed branch when the keys
are integers in a small range.  I don't believe this instruction exists
in 7.1.  In all releases, the undocumented SYS:%JUMP subprimitive
transfers control to a PC.  I do not recommend using it as it's very
easy to get into trouble with it.  I'm not aware of any special form for
converting a GO-tag into a PC value.

				  I also need to be able to compare two
    PCs as integers and determine which is larger before I branch indirectly
    to one of of them. How can I do that?

I don't understand why you would want to do this nor how you would get
your hands on PC values.  However, given that you have two PC values,
the subprimitive SYS:%POINTER-LESSP will compare them, as documented.

I hope you find these suggestions helpful.  If you have more questions,
feel free to ask me.  I may take a few days to respond.  Be sure to copy
Customer-Reports and Discuss-Compiler on all mail.

    Below is a sample piece of code which my SAT translater generates:

    (LAMBDA (ALL?)
      (PROG (RESULTS P0001 P0002 P0003)
	    (SETQ P0001 NIL)
	    (GO N0004)
      F0005 (IF P0001 (RETURN RESULTS))
	    (SETQ P0001 T)
      N0004 (IF (NOT P0001) (GO S0006))
	    (GO F0005)
      S0006 (SETQ P0002 NIL)
	    (GO N0007)
      F0008 (IF P0002 (GO F0005))
	    (SETQ P0002 T)
      N0007 (IF P0001 (GO S0009))
	    (IF (NOT P0002) (GO S0009))
	    (GO F0008)
      S0009 (SETQ P0003 NIL)
	    (GO N0010)
      F0011 (IF P0003 (GO F0008))
	    (SETQ P0003 T)
      N0010 (IF P0002 (GO S0012))
	    (IF (NOT P0003) (GO S0012))
	    (GO F0011)
      S0012 (PUSH (LIST (CONS 'A (IF P0001 :TRUE :FALSE))
			(CONS 'B (IF P0002 :TRUE :FALSE))
			(CONS 'C (IF P0003 :TRUE :FALSE)))
	    (IF ALL? (GO F0011) (RETURN RESULTS))))