Jump to content

Recommended Posts

How can I implement a very efficient "jump table" using BoostC?

 

I am trying to implement a jump table equivalent to this (the code needs to be fast):

 

pcl += value;

goto label1;

goto label2;

goto label3;

etc.

 

I've run into several issues:

1. First I tried function pointers, but they generate bulky code so now I am just trying to add an offset to pcl which will skip to a goto

2. The compiler is removing what it thinks is "dead code" (after the first goto), even with optimization turned off ("-O0")

3. After it removes the "dead code" gotos, it sees unreachable code (the target code fragments) so it removes those also.

 

 

I have tried this with BoostC 7.10, 7.051 and 7.04, with the same results.

Target device is PIC16F1827, '1823, or '688, but I don't think that matters.

O/S: Windows XP, but I don't think that matters.

 

Below is my sample code:

 

--------

//BoostC dead code removal can't be turned off

//this happens with 7.10, 7.051 and 7.04 also (not tested prior to that)

 

 

#include <system.h> //do not use this line for libraries

typedef unsigned char uint8;

 

#pragma OPTIMIZE "0" //this doesn't avoid "dead code" removal

void main(void)

{

uint8 var1, var2;

 

var1 = 1+2; //example; calculate jumptable offset here

 

pcl += var1; //pclath is assumed to already be set correctly

//the following statements are being removed even with optimization turned off:

goto here1;

goto here2;

goto here3;

goto here4;

 

 

//below are example code fragments:

here1: porta = 1; return;

//the following are being removed unless a conditional "goto" to them is added elsewhere:

here2: porta = 2; return;

here3: porta = 3; return;

here4: porta = 4; return;

}

 

--------

 

 

I can defeat the dead code removal by using code such as the following:

 

if (never_zero == 0) goto here1;

if (never_zero == 0) goto here2;

if (never_zero == 0) goto here3;

if (never_zero == 0) goto here4;

 

but this is bulky because it takes 2 instructions for each jumptable entry, and it also needs a left-shift of the jumptable offset variable before it is added to pcl (which is even more overhead).

 

This topic is related to an old post which implied that asm statements would help:

http://forum.sourceb...p?showtopic=680

 

I tried using an asm block:

asm

{

goto here1;

goto here2;

goto here3;

goto here4;

}

 

 

and this preserves the jumptable itself, but the target code fragments are still being removed and then the linker complains that it cannot find the labels - linker error is:

Internal Error: Unable to resolve label ID:268435717 - 0x10000105

 

Turning off linker optimization ("-O0") avoids this error, but that is a global switch and I do not wish to turn off optimization for the entire module.

 

Any other suggestions of how to solve this?

 

thanks

 

don

Share this post


Link to post
Share on other sites

How can I implement a very efficient "jump table" using BoostC?

...

Any other suggestions of how to solve this?

 

 

This is indeed a bit of a problem, no nice way to do it at the moment.

 

Here is a workaround; a bit ugly, and wastes memory, but should be fast.

Note that I also use a fixed address function to make sure that linker doesn't move this code to a location where the jump table crosses a page boundry that would then break the code.

 

#include<system.h>

void foo();

void main()
{
   foo();
   while( 1 );
}

#define LEAVE_CODE_BELOW asm btfsc _x, 0

#pragma OPTIMIZE "0"
void foo() @0x100
{
   unsigned char value = 1;
   bool x = 0;

   value <<= 2;
   value += 2;

   pcl += value;

   LEAVE_CODE_BELOW
   goto label0;
   LEAVE_CODE_BELOW
   goto label1;
   LEAVE_CODE_BELOW
   goto label2;

   LEAVE_CODE_BELOW
   label0: porta = 1; return;

   LEAVE_CODE_BELOW
   label1: porta = 2; return;

   LEAVE_CODE_BELOW
   label2: porta = 3; return;
}

 

I hope that helps.

Share this post


Link to post
Share on other sites

Thanks for the response!

 

Note that I also use a fixed address function to make sure that linker doesn't move this code to a location where the jump table crosses a page boundry that would then break the code.

 

Yes, I am doing that also. I just didn't show it in the example code because it was not directly related to my main question. sorry about that.

 

Here is a workaround; a bit ugly, and wastes memory, but should be fast.

 

 

#define LEAVE_CODE_BELOW asm btfsc _x, 0

 

#pragma OPTIMIZE "0"

void foo() @0x100

{

unsigned char value = 1;

bool x = 0;

 

value <<= 2;

value += 2;

 

pcl += value;

 

LEAVE_CODE_BELOW

goto label0;

LEAVE_CODE_BELOW

goto label1;

LEAVE_CODE_BELOW

goto label2;

 

LEAVE_CODE_BELOW

label0: porta = 1; return;

 

LEAVE_CODE_BELOW

label1: porta = 2; return;

 

LEAVE_CODE_BELOW

label2: porta = 3; return;

}

 

I am actually doing this already on some smaller jumptables, and it works okay. (I used "if (status.Z)" rather than the asm statement, but same idea since the result will never be 0 in my case).

 

The problem I've run into now is that I need a jumptable with more than 128 entries. I can get around that by doing an exploratory add first then check for Carry, then increment pclath before altering pcl, but that gets me back into more overhead and defeats the purpose of doing this in the first place.

 

The only other technique I came up with was to use "call" instead of "goto" and then never return from the called code. This will avoid the need for a dummy "if" in front of each jumptable entry because the compiler thinks there is a path to all of them, but this will only work in main (or anywhere else that does not need a previously pushed return address).

 

I also started to try building the "gotos" manually (ie, "#pragma data 0x2800 + adrs") but something (linker?) would not perform the addition - I just got "2800" ("goto 0") instead of the correct destination address. I'm thinking there might still be a way to force it, but I don't know enough about the limitations of the linker (or maybe second pass of the compiler itself). Do you think there is a possibility there?

 

don

Share this post


Link to post
Share on other sites

djulien,

I also started to try building the "gotos" manually (ie, "#pragma data 0x2800 + adrs") but something (linker?) would not perform the addition - I just got "2800" ("goto 0") instead of the correct destination address. I'm thinking there might still be a way to force it, but I don't know enough about the limitations of the linker (or maybe second pass of the compiler itself). Do you think there is a possibility there?

Compile doesn't know anything about addresses as they are determined by linker when the program is linked.

 

The only way to have knowledge about code (or variable) addresses prior to the linking stage to to make them fixed.

 

I suggest the following:



#define FOO1_ADDR 0x200
#define FOO2_ADDR 0x210
#define FOO3_ADDR 0x220
#define GOTO_OPCODE 0x2800

// build jump table
#pragma DATA 0x100, GOTO_OPCODE + FOO1_ADDR, GOTO_OPCODE + FOO2_ADDR, GOTO_OPCODE + FOO3_ADDR


void foo1()@FOO1_ADDR
{
...
}


void foo2()@FOO2_ADDR
{
...
}



void foo3()@FOO3_ADDR
{
...
}

I hope you get the idea. Its all a bit on the manual side

 

Regards

Dave

Share this post


Link to post
Share on other sites

The only way to have knowledge about code (or variable) addresses prior to the linking stage to to make them fixed.

 

I suggest the following:



#define FOO1_ADDR 0x200
#define FOO2_ADDR 0x210
#define FOO3_ADDR 0x220
#define GOTO_OPCODE 0x2800

// build jump table
#pragma DATA 0x100, GOTO_OPCODE + FOO1_ADDR, GOTO_OPCODE + FOO2_ADDR, GOTO_OPCODE + FOO3_ADDR


void foo1()@FOO1_ADDR
{
...
}


void foo2()@FOO2_ADDR
{
...
}



void foo3()@FOO3_ADDR
{
...
}

I hope you get the idea. Its all a bit on the manual side

 

Dave,

 

Thanks for the reminder about only the linker knowing the addresses, and for this new suggestion to use fixed addresses. I guess that will do what I want, except that I'll also need to make the local variables global so they can be shared by the target code segments, or else put them at fixed addresses also and leave them local (so at least the names won't be defined at global scope).

 

I guess it comes down to how ugly I want to make the code. No worse than using MPASM at this point, I guess - but not much better either (:

 

Is there any equivalent of "$" in BoostC? (ie, is there a way to embed the current address into the final instructions generated by the linker, like for example, "goto $+1" or "movlw $" in MPASM?). That could help avoid a lot of hard-coded addresses defined in the code.

 

thanks

 

don

Share this post


Link to post
Share on other sites

I guess it comes down to how ugly I want to make the code. No worse than using MPASM at this point, I guess - but not much better either (:

Hopefully other language aspects make it seem worthwhile

 

Is there any equivalent of "$" in BoostC? (ie, is there a way to embed the current address into the final instructions generated by the linker, like for example, "goto $+1" or "movlw $" in MPASM?). That could help avoid a lot of hard-coded addresses defined in the code.

No.

 

Regards

Dave

Share this post


Link to post
Share on other sites

Okay, I think I came up with a reasonable work-around. Here is some sample code:

 

#include <system.h>

inline void RETURN(void)

{

asm data 8; //hard-return to caller (via stack)

//NOTE: this "hides" the return so code following this will not be treated like dead code

// "return" will not have the same effect (code following *will* be removed)

}

 

inline void test(void) //@0x100 //normally this should be a fixed address, details omitted for clarity

{

pcl += table_offset;

asm //wrap in asm to avoid dead code removal

{

;NOTE: this even works with compiler -O2, linker -O1 options

;NOTE: works with inline and non-inline functions (but must use hard return)

;NOTE: all sections of code must be referenced here to avoid dead code removal

;NOTE: first label following jumptable must be the first "goto" to avoid dead code removal

;NOTE: first label following jumptable will be ignored after last "goto"

;NOTE: after first "goto", all entries except "goto" and "return" will be removed

;NOTE: "data" stmt will be preserved only before first "goto"

;NOTE: "return" cannot be used before first "goto"; causes dead code removal

;//if you get an error like "//Internal Error: Unable to resolve label ID:268440099 - 0x10001223",

;//it means that one of the code segments was removed because it looked like dead code

;BTW: ASM in lowercase cannot appear within comments (parser bug)

 

data 8; //this will be treated like a return back to caller (thru stack)

goto trailer; //this avoids dead code removal in following code

data 8; //this entry will be dropped

goto second;

return; //empty spot in jump table (returns to caller via stack)

goto trailer;

data 8; //this entry will be dropped

goto first;

data 8; //this entry will be dropped

goto softreturn;

goto trailer; //this entry will be dropped because it points right after jump table

}

 

trailer:

porta = portb +3; //some code here

RETURN();

 

first:

porta = 2; //more code here

RETURN();

 

second:

porta = 3; //more code here

RETURN();

 

softreturn:

if (status.Z) RETURN();

}

 

 

I'm guessing that the reason this works is because it looks close enough to the jump table that is generated for use by function pointers, and so the linker must contain logic to prevent altering that jump table code (or else function pointers won't work). Still, it would be nicer if the compiler/linker officially supported this construct.

 

don

Share this post


Link to post
Share on other sites

Don, if it helps, I used movf _pcl,F in place of goto $+1 recently...

 

Mike,

 

thanks for the tip.

 

In re-reading this, I realize that I gave a bad example, since there are a number of instructions that could replace "goto $+1" (including just a simple nop). I meant "goto $+const", where "const" can be any value known at compile time.

 

However, taking your idea further, I guess I could use "pcl += value" as long as I check that pclath does not overflow.

 

don

Share this post


Link to post
Share on other sites

Join the conversation

You are posting as a guest. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

×
×
  • Create New...