8051 code generation 
Author Message
 8051 code generation

I am thinking about code generation for 8051.

[Problem summary]

A link-on-demand target compiler originally has almost all
Forth words in a source code library. When a not-yet-loaded
word is used, a forward reference is generated, and the
referenced word is put into the automatic link queue.
When ; (semi-colon) executes, such words are linked and
the references are resolved.
This works fine in the case of traditional DTC and ITC.
In the case of STC (subroutine-threaded code) this
also works.

But on a 8051 there are two CALL instructions:

ACALL - call within the current 2K "page", 2 bytes
LCALL - call anywhere, 3 bytes

It is, of course, desirable to generate short CALL
instructions where possible. But we cannot predict
the size and location of forward-referenced
procedures.

[End of problem summary]

Does anybody know / can anybody think out
an algorithm that would allow this sort of optimization
(short CALL instructions for calls within the current 2K page)?
The algorithm may be optimal or sub-optimal;
probably it may be a bit incorrect (so that manual
correction of its behaviour would be possible);
but it must be practical.

(The source code must not contain info about which
calls are local and which are long).

I myself think out optimization at the level of intermediate
code; this has the following disadvantege:
the user definitely knows 8051 code, but he
must be allowed to know nothing about intermediate code.

(I've seen such monsters as "compiling" words that
generate in-line assembly code assuming that some
registers are unused and left intact, for example,
an IFCARRY statement, a FOR..NEXT loop using R6
as the counter, the latter cannot even be nested,
so it is something between Forth and Assembly.
Do not ask me what I really think about this language.
Probably, there is an apology that the code already
is peculiar to the on-board hardware, which also
is not stable but changes from version to version.)

So, introduction of the level of intermediate code
is rather undesirable. The code generation must
remain open. But allow generation of short call
instructions.

Any suggestions?

Regards, Michael



Tue, 03 Sep 2002 03:00:00 GMT  
 8051 code generation
I have in mind a solution that is ugly, but then, to me, everything
about the 8051 is ugly, so maybe it fits.

Generate the code in several passes. At first, use LCALL everywhere.
When the code is complete, check each call for range and convert it to
ACALL if possible, closing the gap each time. The compacting process may
have moved one or more ACALLs into LCALL range. Repeating the compacting
process will catch them.

I can already think of ways that might make this method a little more
efficient, but they aren't worth going into if you think the whole idea
is out of the question.

Jerry
--
Engineering is the art of making what you want from things you can get.
-----------------------------------------------------------------------

Quote:

> I am thinking about code generation for 8051.

> [Problem summary]

> A link-on-demand target compiler originally has almost all
> Forth words in a source code library. When a not-yet-loaded
> word is used, a forward reference is generated, and the
> referenced word is put into the automatic link queue.
> When ; (semi-colon) executes, such words are linked and
> the references are resolved.
> This works fine in the case of traditional DTC and ITC.
> In the case of STC (subroutine-threaded code) this
> also works.

> But on a 8051 there are two CALL instructions:

> ACALL - call within the current 2K "page", 2 bytes
> LCALL - call anywhere, 3 bytes

> It is, of course, desirable to generate short CALL
> instructions where possible. But we cannot predict
> the size and location of forward-referenced
> procedures.

> [End of problem summary]

> Does anybody know / can anybody think out
> an algorithm that would allow this sort of optimization
> (short CALL instructions for calls within the current 2K page)?
> The algorithm may be optimal or sub-optimal;
> probably it may be a bit incorrect (so that manual
> correction of its behaviour would be possible);
> but it must be practical.

> (The source code must not contain info about which
> calls are local and which are long).

> I myself think out optimization at the level of intermediate
> code; this has the following disadvantege:
> the user definitely knows 8051 code, but he
> must be allowed to know nothing about intermediate code.

> (I've seen such monsters as "compiling" words that
> generate in-line assembly code assuming that some
> registers are unused and left intact, for example,
> an IFCARRY statement, a FOR..NEXT loop using R6
> as the counter, the latter cannot even be nested,
> so it is something between Forth and Assembly.
> Do not ask me what I really think about this language.
> Probably, there is an apology that the code already
> is peculiar to the on-board hardware, which also
> is not stable but changes from version to version.)

> So, introduction of the level of intermediate code
> is rather undesirable. The code generation must
> remain open. But allow generation of short call
> instructions.

> Any suggestions?

> Regards, Michael



Tue, 03 Sep 2002 03:00:00 GMT  
 8051 code generation
: I am thinking about code generation for 8051.

: [Problem summary]

: Does anybody know / can anybody think out
: an algorithm that would allow this sort of optimization
: (short CALL instructions for calls within the current 2K page)?

Instead of generating a forward reference, each time you discover a
word that hasn't yet been compiled, back off the dictionary pointer to
the start of the current definition, compile the referenced word, and
then start again.  That way, all calls are backward calls, and as much
as possible they're mostly near calls.

You'd have to detect deadlock caused by mutual recursion, but that's a
fairly straightforward thing to do.  In that case, you would have to
generate a forward reference.

Andrew.



Tue, 03 Sep 2002 03:00:00 GMT  
 8051 code generation

Quote:

> I have in mind a solution that is ugly, but then, to me, everything
> about the 8051 is ugly, so maybe it fits.
:-)

> Generate the code in several passes. At first, use LCALL everywhere.
> When the code is complete, check each call for range and convert it to
> ACALL if possible, closing the gap each time. The compacting
> process may
> have moved one or more ACALLs into LCALL range.

Yes,

 ........   | a: ..... ACALL a ... |

may become

 .... a: .. | .... ACALL a ....... |

(bars "|" denote page boundaries)

Quote:
> Repeating the compacting
> process will catch them.

I would say, an expanding pass, but again something might
move so that

  | ... ACALL b ..... b: ..|...

becomes

  | ........ ACALL b ......|. b: ..

Quote:

> I can already think of ways that might make this method a little more
> efficient,

Yes, please!

Quote:
> but they aren't worth going into if you think the whole idea
> is out of the question.

I am also thinking in this direction.

What I can think out is auxiliary information in a separate
datastructure residing on the disk.
Recompilation may give more compact code, provided that
a way is found to guarantee that the process finishes.

Quote:

> Jerry
> --
> Engineering is the art of making what you want from things you
> can get.

Sent via Deja.com http://www.deja.com/
Before you buy.


Tue, 03 Sep 2002 03:00:00 GMT  
 8051 code generation

Quote:

> I am thinking about code generation for 8051.

> [Problem summary]

> A link-on-demand target compiler originally has almost all
> Forth words in a source code library. When a not-yet-loaded
> word is used, a forward reference is generated, and the
> referenced word is put into the automatic link queue.
> When ; (semi-colon) executes, such words are linked and
> the references are resolved.
> This works fine in the case of traditional DTC and ITC.
> In the case of STC (subroutine-threaded code) this
> also works.

> But on a 8051 there are two CALL instructions:

> ACALL - call within the current 2K "page", 2 bytes
> LCALL - call anywhere, 3 bytes

> It is, of course, desirable to generate short CALL
> instructions where possible. But we cannot predict
> the size and location of forward-referenced
> procedures.

> [End of problem summary]

> Does anybody know / can anybody think out
> an algorithm that would allow this sort of optimization
> (short CALL instructions for calls within the current 2K page)?
> The algorithm may be optimal or sub-optimal;
> probably it may be a bit incorrect (so that manual
> correction of its behaviour would be possible);
> but it must be practical.

On a transputer it is worse, each call has just the needed amount
of nibbles to reach the target (1 to 8). What we do is to "guess" in
pass n what the size of the offset will be. In pass n+1 this "guess" is
improved. In a naive implementation one simply compiles the source again,
using the adjusted symboltable (a few more symbols get the 'short'
attribute). Stop when the generated code does not become smaller (or when
the number of passes indicates a limit cycle). I don't think it is possible
to predict how many passes are needed. On the transputer / iForth I observe
between 5 and 8 (about 8 seconds compile time on a P55-166).

-marcel



Tue, 03 Sep 2002 03:00:00 GMT  
 8051 code generation

Quote:


> : Does anybody know / can anybody think out
> : an algorithm that would allow this sort of optimization
> : (short CALL instructions for calls within the current 2K page)?

> Instead of generating a forward reference, each time you discover a
> word that hasn't yet been compiled, back off the dictionary pointer to
> the start of the current definition, compile the referenced word, and

recursively...

I would rather compile to a buffer, but then I would need relocation.
In addition, there would be a problem with

\ I am too lazy to write code for list construction here&now
COMPILER
VARIABLE counter

TARGET
LIBRARY
// foo
: foo DUP SWAP DROP .id ." foo is running! " CR ;
// bar
: bar ...

I want to say that library entries may update global datastructures,
and updating them twice may be not the same as updating them once.
OTOH, this could be prohibited, but OTTH in the existing version
it is allowed.

Quote:
> then start again. That way, all calls are backward calls, and as much
> as possible they're mostly near calls.

If the 1st word is a complex : definition, we may get
the folowing:

Initially

 | xxx                  |

Finally with this approach

 | xxx    DUP SWAP DROP | complex-word

instead of

 | xxx complex-word DUP | SWAP DROP

In the latter case SWAP and DROP still may be
called with ACALL.

So, the always-call-backward approach is not so good.

Quote:

> You'd have to detect deadlock caused by mutual recursion, but that's a
> fairly straightforward thing to do. In that case, you would have to
> generate a forward reference.

> Andrew.

Sent via Deja.com http://www.deja.com/
Before you buy.


Tue, 03 Sep 2002 03:00:00 GMT  
 8051 code generation



: > : Does anybody know / can anybody think out
: > : an algorithm that would allow this sort of optimization
: > : (short CALL instructions for calls within the current 2K page)?
: >
: > Instead of generating a forward reference, each time you discover a
: > word that hasn't yet been compiled, back off the dictionary pointer to
: > the start of the current definition, compile the referenced word, and

: recursively...

Yeah.  :-)

: In addition, there would be a problem with

: \ I am too lazy to write code for list construction here&now
: COMPILER
: VARIABLE counter

: TARGET
: LIBRARY
: // foo
: : foo DUP SWAP DROP .id ." foo is running! " CR ;
: // bar
: : bar ...

Why's that a problem?

: I want to say that library entries may update global datastructures,

Well, that's obviously bad.  Loading code from a library should be an
idempotent opration or you're just asking for trouble.

: > then start again. That way, all calls are backward calls, and as much
: > as possible they're mostly near calls.

: If the 1st word is a complex : definition, we may get
: the folowing:

[ ... ]

: In the latter case SWAP and DROP still may be
: called with ACALL.

What would tend to happen is that all the common words would be
compiled early.  It's not a perfect approach, but it's pretty good.  I
would expect that finding an ideal solution is an NP-complete problem.

Andrew.



Tue, 03 Sep 2002 03:00:00 GMT  
 8051 code generation

Michael:
Not sure I understand your problem but the attached
file is one I use to handle branches and calls when I
hand assembly F68HC11 programs.  Maybe the idea
will work for your requirement.
Bill S.

Quote:

> I am thinking about code generation for 8051.

> [Problem summary]

> Any suggestions?

> Regards, Michael

[ Mc 2K ]
( FILE MC                                               05 SEP  1988

( HEADERLESS

( This file has helper words that are used in hand coding machine
( code for the F68HC11.  When used, the file should be loaded before
( the machine code source file is loaded.  As a test and demonstration
( these words were used in a revised version of the SCI file, dated
( 02 SEP 1988.  File MC.DOC discusses the application of these words
( using the SCI file as a demonstration.

( RANDY DUMSE, NEW MICROS, INC is responsible for the suggestion that
( provided the idea for this coding.

( ---  adr1   The function of this word is to store a 0 byte in the branch
(      value of a branch instruction and leave the address of the 0 on
(      the data stack for later use in updating the branch value.
(      "Need 1"

: N1     HERE 0 C, ;

( adr1 ---    The function of this word is to replace the 0 byte branch
(      value at adr1 with the appropriate branch value to reach the
(      current location in the compiled code.
(      "Located 1"

: L1     HERE OVER 1+ - SWAP C! ;

( --- adr1   The function of this word is to save the present location
(            address, on the data stack, so it may be used by LB1 for
(            a backward branch byte value computation.
(            " Save 1"

: S1     HERE  ;

( adr1 ---  The function of this word is to computer a backward branch
(           byte value to the adr1 value previously saved on the data stack.
(           " Located Backward 1"

: LB1    HERE 1+ - C, ;

( --- adr1  The function of this word is to store a 0 cell, 16 bits, as
(           the JMP address for a JMP EXT instruction and leave the
(           address of the 0 location on the data stack for later use
(           in updating the JMP value
(           " Need Jump"

: NJ    HERE 0 , ;

( adr1 ---  The function of this word is to replace the 0 cell JMP
(           address value at adr1 with the appropriate address of the
(           current dictionary pointer.
(           "Located Jump"

: LJ    HERE SWAP ! ;

( --- adr1  The function of this word is to store the current dictionary
(           address on the Data Stack, adr1, so it may be used by a
(           backward JMP instruction that has not yet been defined in
(           the source code.
(           "Jump Back"

: JB    HERE ;

( adr1 ---  The function of this work is to implement a backward JMP
(           instruction to the address, adr1, on the Data Stack.
(           "Located Jump Back"

: LBJ    , ;

( --- adr  This word is used during compile, to provide the literal
(          address of a counted text string to be later displayed.




Wed, 04 Sep 2002 03:00:00 GMT  
 8051 code generation

Michael:
Not sure I understand your problem but the attached
file is one I use to handle branches and calls when I
hand assembly F68HC11 programs.  Maybe the idea
will work for your requirement.
Bill S.

Quote:

> I am thinking about code generation for 8051.

> [Problem summary]

> Any suggestions?

> Regards, Michael

[ Mc 2K ]
( FILE MC                                               05 SEP  1988

( HEADERLESS

( This file has helper words that are used in hand coding machine
( code for the F68HC11.  When used, the file should be loaded before
( the machine code source file is loaded.  As a test and demonstration
( these words were used in a revised version of the SCI file, dated
( 02 SEP 1988.  File MC.DOC discusses the application of these words
( using the SCI file as a demonstration.

( RANDY DUMSE, NEW MICROS, INC is responsible for the suggestion that
( provided the idea for this coding.

( ---  adr1   The function of this word is to store a 0 byte in the branch
(      value of a branch instruction and leave the address of the 0 on
(      the data stack for later use in updating the branch value.
(      "Need 1"

: N1     HERE 0 C, ;

( adr1 ---    The function of this word is to replace the 0 byte branch
(      value at adr1 with the appropriate branch value to reach the
(      current location in the compiled code.
(      "Located 1"

: L1     HERE OVER 1+ - SWAP C! ;

( --- adr1   The function of this word is to save the present location
(            address, on the data stack, so it may be used by LB1 for
(            a backward branch byte value computation.
(            " Save 1"

: S1     HERE  ;

( adr1 ---  The function of this word is to computer a backward branch
(           byte value to the adr1 value previously saved on the data stack.
(           " Located Backward 1"

: LB1    HERE 1+ - C, ;

( --- adr1  The function of this word is to store a 0 cell, 16 bits, as
(           the JMP address for a JMP EXT instruction and leave the
(           address of the 0 location on the data stack for later use
(           in updating the JMP value
(           " Need Jump"

: NJ    HERE 0 , ;

( adr1 ---  The function of this word is to replace the 0 cell JMP
(           address value at adr1 with the appropriate address of the
(           current dictionary pointer.
(           "Located Jump"

: LJ    HERE SWAP ! ;

( --- adr1  The function of this word is to store the current dictionary
(           address on the Data Stack, adr1, so it may be used by a
(           backward JMP instruction that has not yet been defined in
(           the source code.
(           "Jump Back"

: JB    HERE ;

( adr1 ---  The function of this work is to implement a backward JMP
(           instruction to the address, adr1, on the Data Stack.
(           "Located Jump Back"

: LBJ    , ;

( --- adr  This word is used during compile, to provide the literal
(          address of a counted text string to be later displayed.




Wed, 04 Sep 2002 03:00:00 GMT  
 8051 code generation

Michael:
Not sure I understand your problem but the attached
file is one I use to handle branches and calls when I
hand assembly F68HC11 programs.  Maybe the idea
will work for your requirement.
Bill S.

Quote:

> I am thinking about code generation for 8051.

> [Problem summary]

> Any suggestions?

> Regards, Michael

[ Mc 2K ]
( FILE MC                                               05 SEP  1988

( HEADERLESS

( This file has helper words that are used in hand coding machine
( code for the F68HC11.  When used, the file should be loaded before
( the machine code source file is loaded.  As a test and demonstration
( these words were used in a revised version of the SCI file, dated
( 02 SEP 1988.  File MC.DOC discusses the application of these words
( using the SCI file as a demonstration.

( RANDY DUMSE, NEW MICROS, INC is responsible for the suggestion that
( provided the idea for this coding.

( ---  adr1   The function of this word is to store a 0 byte in the branch
(      value of a branch instruction and leave the address of the 0 on
(      the data stack for later use in updating the branch value.
(      "Need 1"

: N1     HERE 0 C, ;

( adr1 ---    The function of this word is to replace the 0 byte branch
(      value at adr1 with the appropriate branch value to reach the
(      current location in the compiled code.
(      "Located 1"

: L1     HERE OVER 1+ - SWAP C! ;

( --- adr1   The function of this word is to save the present location
(            address, on the data stack, so it may be used by LB1 for
(            a backward branch byte value computation.
(            " Save 1"

: S1     HERE  ;

( adr1 ---  The function of this word is to computer a backward branch
(           byte value to the adr1 value previously saved on the data stack.
(           " Located Backward 1"

: LB1    HERE 1+ - C, ;

( --- adr1  The function of this word is to store a 0 cell, 16 bits, as
(           the JMP address for a JMP EXT instruction and leave the
(           address of the 0 location on the data stack for later use
(           in updating the JMP value
(           " Need Jump"

: NJ    HERE 0 , ;

( adr1 ---  The function of this word is to replace the 0 cell JMP
(           address value at adr1 with the appropriate address of the
(           current dictionary pointer.
(           "Located Jump"

: LJ    HERE SWAP ! ;

( --- adr1  The function of this word is to store the current dictionary
(           address on the Data Stack, adr1, so it may be used by a
(           backward JMP instruction that has not yet been defined in
(           the source code.
(           "Jump Back"

: JB    HERE ;

( adr1 ---  The function of this work is to implement a backward JMP
(           instruction to the address, adr1, on the Data Stack.
(           "Located Jump Back"

: LBJ    , ;

( --- adr  This word is used during compile, to provide the literal
(          address of a counted text string to be later displayed.




Wed, 04 Sep 2002 03:00:00 GMT  
 8051 code generation

Michael:
Not sure I understand your problem but the attached
file is one I use to handle branches and calls when I
hand assembly F68HC11 programs.  Maybe the idea
will work for your requirement.
Bill S.

Quote:

> I am thinking about code generation for 8051.

> [Problem summary]

> Any suggestions?

> Regards, Michael

[ Mc 2K ]
( FILE MC                                               05 SEP  1988

( HEADERLESS

( This file has helper words that are used in hand coding machine
( code for the F68HC11.  When used, the file should be loaded before
( the machine code source file is loaded.  As a test and demonstration
( these words were used in a revised version of the SCI file, dated
( 02 SEP 1988.  File MC.DOC discusses the application of these words
( using the SCI file as a demonstration.

( RANDY DUMSE, NEW MICROS, INC is responsible for the suggestion that
( provided the idea for this coding.

( ---  adr1   The function of this word is to store a 0 byte in the branch
(      value of a branch instruction and leave the address of the 0 on
(      the data stack for later use in updating the branch value.
(      "Need 1"

: N1     HERE 0 C, ;

( adr1 ---    The function of this word is to replace the 0 byte branch
(      value at adr1 with the appropriate branch value to reach the
(      current location in the compiled code.
(      "Located 1"

: L1     HERE OVER 1+ - SWAP C! ;

( --- adr1   The function of this word is to save the present location
(            address, on the data stack, so it may be used by LB1 for
(            a backward branch byte value computation.
(            " Save 1"

: S1     HERE  ;

( adr1 ---  The function of this word is to computer a backward branch
(           byte value to the adr1 value previously saved on the data stack.
(           " Located Backward 1"

: LB1    HERE 1+ - C, ;

( --- adr1  The function of this word is to store a 0 cell, 16 bits, as
(           the JMP address for a JMP EXT instruction and leave the
(           address of the 0 location on the data stack for later use
(           in updating the JMP value
(           " Need Jump"

: NJ    HERE 0 , ;

( adr1 ---  The function of this word is to replace the 0 cell JMP
(           address value at adr1 with the appropriate address of the
(           current dictionary pointer.
(           "Located Jump"

: LJ    HERE SWAP ! ;

( --- adr1  The function of this word is to store the current dictionary
(           address on the Data Stack, adr1, so it may be used by a
(           backward JMP instruction that has not yet been defined in
(           the source code.
(           "Jump Back"

: JB    HERE ;

( adr1 ---  The function of this work is to implement a backward JMP
(           instruction to the address, adr1, on the Data Stack.
(           "Located Jump Back"

: LBJ    , ;

( --- adr  This word is used during compile, to provide the literal
(          address of a counted text string to be later displayed.




Wed, 04 Sep 2002 03:00:00 GMT  
 8051 code generation
Your browser is sending repeats (3) of the original message at 1 to 4 min
intervals. Better check it out.

Walter Rottenkolber
------------------------------

Quote:

>Michael:
>Not sure I understand your problem but the attached
>file is one I use to handle branches and calls when I
>hand assembly F68HC11 programs.  Maybe the idea
>will work for your requirement.
>Bill S.


>> I am thinking about code generation for 8051.

>> [Problem summary]

>> Any suggestions?

>> Regards, Michael



Wed, 04 Sep 2002 03:00:00 GMT  
 
 [ 12 post ] 

 Relevant Pages 

1. 8051 simulator - is example code available?

2. An 8051 simulator - is example code available?

3. where can i get 8051 verilog source code

4. fft code for 8051

5. 8051 asm code

6. Instruction Code 8051

7. Asking Help for Intel 8051 code

8. Wanted: Source code for CODE-BAR39 generation

9. I need help in intel 8051

10. looking for a basic compiler for an 8051 uP

11. Payne's 8051 Forth system

12. 8051 disassembler update

 

 
Powered by phpBB® Forum Software