PIC Port to SDCC

SDCC - Small Device C Compiler At Source Forge.

Log:

21MAR04 - I don't work on SDCC regularly anymore. Please see the SDCC Web Page for current SDCC information.

09SEP02 - From this page, it may look like nothing is happening in the PIC Port of SDCC. Well, that's because I quit updating this page. The PIC port is essentially beta quality at this point. There are still problems, and I'm still fixing them. To get the latest info please check out the SDCC webpage. Also, you may wish to join the SDCC mailing list or the GNUPIC mailing list.

16oct01 - Bunch of stuff

I've been hacking away at SDCC quite a bit. Some of the major new things:

24sep01 - Shift left by a constant now works.

Tail Optimizations (part 1: Unused Labels are now removed)

While working on the rotate code, I came across an optimization. Consider this code:

    ...
    goto    label1
    ...

label1
    return

this can be replaced by:

    ...
    return
    ...

;label1
;    return

This is a specific example of the generic class of "tail optimizations". These are optimizations that remove redundant exit code. I'll be working in this area next.

The first step of this has been implemented. It was necessary to remove redundant and/or unused labels.

18SEP01 - I spent most of the summer working on gpsim. I started back on SDCC in ernest a few weeks ago and here's where things stand:

07MAY01 - Parsing assembly to create pCode. One of the features introduce by the PIC Port of SDCC is "pCode". (See the logs below for a detailed description - but in short, pCode is the post code generation optimization.) One of the tasks it must perform is the parsing of text files that contain "peep hole" snippets. These peep hole snippets consist of two blocks of assembly code: the first is a "target" while the second is a "replace". The peephole optimizer searches the code SDCC generates for lines of code that match the "target". If a match is found, it's (conditionally) replaced.

Prior to the pCode optimizer, SDCC would perform a text based search for the targets. However, there are certain advantages gained by performing the comparison using pCodes. One advantage is that it's possible to ascertain program flow and state information. Certain snippets may be applicable for different states of the PIC (or other) microcontroller. So now the pCode optimizer is responsible for parsing these snippets.

But if you think about it, parsing these snippets to generate pCode is essentially the function of an Assembler. I had thought about merging gpasm into SDCC, however this has a few draw backs. The most significant is that SDCC targets microcontrollers other than the pic, but gpasm doesn't. Secondly, gpasm is overkill. All that's needed is a simple one-line assembler. So I wrote one.

Below is an example of a peep hole assembly line being parsed:

%4:      movf    %1,w
 pct % num  col : space  str  space  pct % num  com , str 
  label
  movf is  mnem
  1st operand is wild
  got a comma
  w is  2 operands
altpat_label with ID = 4
altpat_mnem2a movf var 1 destination w(0)
  MOVF    %1,W

The first line is the raw text from the peep hole file. The "%" is the SDCC wild card place holder indicator. For example, in a sequence of assembly lines, a "%N" will get replaced with a string of text. (BTW, prior to pCode, the %N's only applied to variables and labels, now they can also apply to menmonics.) The second line is debug dump of the tokens parsed out from the assembly string. The 3rd through 7th lines are the states extracted form certain token sequences. The 8'th and 9'th lines (beginning with "altpat") are printed by call back functions that are invoked when assembly lines patterns are recognized. ("alt" stands for: assembly line type.) Finally, the last line is the result of a call to the pCode->print() call back function.

This example illustrates that the "assembler" works. (The label is buried somewhere else and not printed... but it's hidden in there!) The next step will be to mull through the details so that I can again get back into generating PIC code!

01APR01 - 10,000 lines of code in one file is too many. This is the case with the PIC Port's gen.c (most of which I inherited). So, I've split it into two files by separating the arithmetic generation. pcode.c is also slowly growing into an unmanageable beast. So I split that into two files by removing all of the peep hole optimization.

As far as functionality, I've added unsigned char and integer and bit subtraction. There's a new regression file 'sub.c'.

I've also introduced structure support. The regression file associated with it is struct1.c. The emphasis here needs to be on the word 'introduced'. Individually elements of structures can be accessed and manipulated. Also, it's possible to pass a pointer to structure as a parameter in a function. (Probably the way structures will be used).

The next thing I'm going to work on is parsing peep.def to generate pcode. This will involve adding the basic function of an assembler to SDCC!

24MAR01 - pCode peephole optimization and register allocation are now working.

Here lately I've been concentrating on pCode optimization. pCode, as you may recall, is "post" code (SDCC already has intermediate code called iCode). There are pCode objects for the various types of code that can be generated. For example, labels, assembly instructions, and comments are the common pCode types. For the assembly instructions, there is a one-to-one correspondence between one pCode object and one instruction. This is useful for analyzing program flow.

The first step in pCode optimization was to mimick, but enhance the peep hole optimization that SDCC already performs. The example that I like to give is this (also see the log entry for 21JAN below):

  movwf  reg
  movf   reg,w

In this example, it's not obvious that the second instruction can be removed. True, W is not changed by the second instruction, but the Z bit in the status register is. The pCode peep hole optimizer handles this situation by examining the instructions that follow the "movf reg,w" instruction. If it's determined that the Z bit is modified by a subsequent instruction before it is tested as an input (e.g. btfsc status,z), then the "movf" can be removed.

The pCode peep hole optimizer works well, but is not completed. The big piece missing is the parsing of peephole definition files. When the pCode stabilizes, I'll integrate it into the src/ directory and will modify SDCCpeeph.c to generate pCode too.

The second step in pCode optimization is register optimization. This is working now! Essentially what it does is traverse the entire call tree and look for register collisions. If a register is being used in a function that is called, then the callee will relocate its register(s). There are at least two major benefits with this feature. First, all local storage can be predetermined and allocated from a pool of registers. Second, a function's local storage doesn't have to be pushed onto a stack when ever another function is called. This is especially good for the pic since it doesn't have a data stack (in fact that was the primary motivation for adding this feature).

The example I've been using to develop the code is:


void inc(unsigned char k)
{
  uchar0 = uchar0 + k;
}

void f1(void)
{

  uchar2++;
}

void nested_call(unsigned char u)
{

  f1();
  uchar1 = uchar1 + u;
  inc(uchar1);

}

'nested_call' is called from main().

It might appear that there is no local storage in these functions. However `inc' and `nested_call' save the calling parameter in a local register. (Or more accurately, the parameter is passed to the function via W and saved locally.) The code that is generated (and which has a bunch of room to be optimized) is:


_nested_call    ;Function start
        MOVWF   r0x0D
        CALL    _f1
        MOVF    r0x0D,W
        ADDWF   _uchar1,F
        MOVF    _uchar1,W
        CALL    _inc
_00201_DS_
        RETURN  

_f1     ;Function start
        INCF    _uchar2,F
_00181_DS_
        RETURN  

_inc    ;Function start
        MOVWF   r0x0C
        ADDWF   _uchar0,F
_00161_DS_
        RETURN  

In this example, the local variable `r0x0D' in nested_call was originally r0x0C (originally, that is, before register optimization kicked in).

The next step will be to add `live ranges' to the logic. In some respects, the above example is poor because the local variables don't actually collide. Furthermore, the example also clearly illustrates that the register optimizer does not remove unnecessary registers. "inc" has no business tucking its input parameter away in local.

Another feature that sounds difficult but in fact will be straight forward is function inlining. Again with the example above, there's no reason that `f1' shouldn't be inlined. If it were, then the call to "inc" could also be removed since "inc" would then immediately "nested_call".

17FEB01 - pCode is alive in CVS. I've begun the pCode optimizer now.

12FEB01 - The pCode infrastructure is slowly coming to life! (see the log entry 21JAN01 below). All of the test cases in the regression directory are now compiled through the pCode method. Whew, now that was a lot of work! The next step is to take over from where I left off a month ago and start generating assembly code.

The pCode so far only analyzes the program flow. In other words, function boundaries are recorded and jumps and skips are linked to their destinations. As a consequence, it's now possible to dump the program call tree. Functions have been written to allow the flow tree to be parsed. For example, to find a particular label one may call this function (which is really only being to show that the pCode is not vapor ware!) :

/*-----------------------------------------------------------------*/
/* findLabel - Search the pCode for a particular label             */
/*-----------------------------------------------------------------*/
pCode * findLabel(pCodeOpLabel *pcop_label)
{
  pBlock *pb;
  pCode  *pc;

  if(!the_pFile)
    return NULL;

  for(pb = the_pFile->pbHead; pb; pb = pb->next) {
    for(pc = pb->pcHead; pc; pc = pc->next) {
      if(pc->type == PC_LABEL) {
      if( ((pCodeLabel *)pc)->key ==  pcop_label->key)
        return pc;
      }
    }
  }

  fprintf(stderr,"Couldn't find label %s", pcop_label->pcop.name);
  return NULL;
}

The details of this function aren't too important at the moment. But it's a good indication of some of the pCode structures that have been created.

The pCode has been designed to include register information as well. I'll be using this information to determine how the register usage and allocation can be optimized. More details on this as it becomes real.

21JAN01 - Frustrated with the limitations of a peep hole optimizer, I'm writing a "pCode optimizer" for SDCC. The peep hole optimizer looks for snippets of code that can be replaced by smaller snippets (or possibly removed altogether). However, it's unable to perform some simple post compile optimizations. Consider

    movwf   temp
    movf    temp,w

At first glance it appears that the movf is unecessary. 9 times out of ten it probably is. However, don't forget that the movf instruction modifies the Z flag in the status register. So a peep hole optimizer can't safely remove the movf without looking at the code that follows. Unfortunately, the number of possibilities to examine grow enormous!

The pCode optimizer is a post compiler optimizer that can examine the state of the assembly program and determine what code can be replaced, removed, or rearranged. It's called "pCode" because it's analogous to "iCode", the intermediate code optimizer. Current versions of SDCC turn the iCode into assembly code by creating lines of text and writing them to a file. In the pCode optimizer, each line of assembly code from comments, to labels, to instructions is allocated it's on pCode structure. These are placed into linked lists instead of written to the assembly file. Once the pCode optimize passes through the linked lists, it will generate the ASCII strings and write them to the assembly file. After this, the normal peep hole optimizer is free to pick over the pieces, but by the time pCode optimizer is done there is nothing but meat left - all the fat has been chewed away.

10JAN01 - I've been spending some time getting register overlays to work. You can see some of this in action in add.c and it's compiled result add.lst. In this example, there are two registers r0x0C and r0x0D that serve as temporary working registers that get reused by the various functions. You can also see in this example some of the good and bad in the C-compiler. It still does some of those stupid things that you see in all compilers. But trust me, I've been stomping these things out whenever possible. (NOTE: These stupid things are not because of the SDCC engine. Instead, they're because I still don't fully understand all of SDCC intricacies.)

31DEC00 - I finally have a new ISP and hence CVS access to SDCC again. All of the changes made over the last few weeks have been commit'd to CVS.

26DEC00 - I've moved back to California and have resumed development. The last few weeks, as you can imagine, have been slow. I still don't have an ISP so am unable to commit my changes but here's what's working so far: for loops, while loops, addition between bit/char/ints, pointers, case statements, and arrays. I still have all of the operators to work out. However, I've concentrated on addition with the idea that others should be similar. Once I think the other stuff is really stable, I'll go back to the other operators.

04DEC00 - Even though it's ugly, I've gone ahead and commit'd the PIC port to SDCC's CVS. So if you really want to look at it, then go ahead and check it out of CVS. See SDCC's home page for instructions on checking out code from CVS.

The == and != operators are working. Look at how tightly SDCC compiles compare.c into compare.lst (ignore the verbose debugging comments...)

27NOV00 - Out of town for most of Thanksgiving. The regression testing infrastructure is in place. The comparison operators are being developed.

18NOV00 - Started the web page.

gpasm file format outputs are almost complete. Good news is that gpasm can be used to compile the code. Bad news is that gpasm doesn't do any linking. But for the time being, that's the way it's going to be. This way I can create scripts that take the output of SDCC, assemble it with gpasm and test the accuracy by simulating with gpsim (in command line mode of course).

casting from smaller to larger types is now supported. There are some 8051 assumptions that during casting SDCC makes in generating the intermediate code that are inappropriate for the PIC. Or I should say it's appropriate, but can be done much more efficiently with the PIC assembly language. Unfortunately, changing this logic means diving into the guts of SDCC - something I'm going to avoid until later.

bit addition is supported.

I think all of the addition cases are tested. However, I'm going to get the testing infrastructure with gpsim established before I migrate to the other operators.

links:

gpsim.

gpasm.

This page is maintained by Scott Dattalo. You can reach me at home: scott@dattalo.com
Last modified on 01APR01.