Menu
▾
▴
anyc-devel
|
From: Patrick E. <pa...@pa...> - 2001-07-17 07:25:46
|
I've been investigating the elusive problem of doing recursion on
these chips. I decided I'd look to see how other compilers did it.
It turns out that NO compilers implement recursion on the PIC chips.
It really isn't that practical in any case. It could probably be
done via some trickery, but the results would be rather useless.
Recursion isn't really a demanded feature for such a small system in
any case. My current thoughts are to issue a warning if a recursive
call is used, and otherwise basically not support recursion for the
PIC. Does this seem like a decent way to go?
Patrick Earl
|
|
From: Daniel W. <dan...@ro...> - 2001-07-18 07:05:45
|
> I've been investigating the elusive problem of doing recursion on > these chips. I decided I'd look to see how other compilers did it. > It turns out that NO compilers implement recursion on the PIC chips. > It really isn't that practical in any case. It could probably be > done via some trickery, but the results would be rather useless. > Recursion isn't really a demanded feature for such a small system in > any case. My current thoughts are to issue a warning if a recursive > call is used, and otherwise basically not support recursion for the > PIC. Does this seem like a decent way to go? I have looked into this in the past. You definitely can't do it easily= ,=20 because the PICs are designed to use the hardware stack. To impliment a=20 software stack (which is what is needed for recursion), it is nice to be = able=20 to read the program counter. If you allow your code to be non-relocatabl= e,=20 the compiler will know the absolute address of all the commands, and thus= the=20 program counter for each command. It would then theoretically be possibl= e to=20 save the high bits of the program counter somewhere. This would be quite= =20 tedious, it seems to me. The AVR line, on the other hand, seems to allow reading of the PC in an= =20 indirect way: if you call a function, the address is pushed (in two bytes= )=20 onto the stack. You can then pop the stack into register space and play = with=20 it. This makes a true software stack for both code and data possible. Have you had a chance to look at the AVR datasheets yet? I'm looking a= t=20 the instruction set doc, and the 90S1200 and 90S8535 (doc is the same as=20 90S4433). =20 I'm unsure how hard it would be to make the compiler work for both=20 situations... maybe not that hard. |
|
From: Patrick E. <pa...@pa...> - 2001-07-18 08:35:12
|
On Wednesday 18 July 2001 00:07, you wrote:
> I have looked into this in the past. You definitely can't do it
> easily, because the PICs are designed to use the hardware stack.
> To impliment a software stack (which is what is needed for
> recursion), it is nice to be able to read the program counter. If
> you allow your code to be non-relocatable, the compiler will know
> the absolute address of all the commands, and thus the program
> counter for each command. It would then theoretically be possible
> to save the high bits of the program counter somewhere. This would
> be quite tedious, it seems to me.
>
> The AVR line, on the other hand, seems to allow reading of the PC
> in an indirect way: if you call a function, the address is pushed
> (in two bytes) onto the stack. You can then pop the stack into
> register space and play with it. This makes a true software stack
> for both code and data possible.
>
> Have you had a chance to look at the AVR datasheets yet? I'm
> looking at the instruction set doc, and the 90S1200 and 90S8535
> (doc is the same as 90S4433).
>
> I'm unsure how hard it would be to make the compiler work for
> both situations... maybe not that hard.
I would be interested in making it possible to work with both
situations. I imagine it would be possible to do with some sort of
generic variable request system. If you need a variable, you ask it
for code to get to that variable. It decides if it's going to be
local or global in scope based on if the processor supports local
variables/recursion. I haven't thought about it that much yet.
The AVR line sounds pretty good for compilers. I wonder if they had
compilers in mind when they were designed. Perhaps to act more like
regular computers. I don't want to only support the AVR line though,
especially since I don't even know if I can easily aquire them
locally without special ordering them. The PIC is a popular chip,
and having a free compiler for it couldn't hurt at all. :) I didn't
look at the datasheets for the AVR chips. I suppose they support
20MHz as well? That was the only question I had about them. Perhaps
I should take a look when thinking about these memory allocation
issues.
Patrick Earl
|
|
From: Daniel W. <dan...@ro...> - 2001-07-18 19:47:10
|
> I would be interested in making it possible to work with both > situations. I imagine it would be possible to do with some sort of > generic variable request system. If you need a variable, you ask it > for code to get to that variable. It decides if it's going to be > local or global in scope based on if the processor supports local > variables/recursion. I haven't thought about it that much yet. I think you may be getting two different things confused, or else I don= 't=20 understand what you're saying. Since the PICs have separate data and cod= e=20 memory, there are separate data and code stacks. You can still implement= a=20 data stack (up to 256 bytes) with the PICs. In fact, I really don't see = any=20 other way to make a proper C compiler except to use a data stack. The re= ason=20 is: the compiler has no way to know what way the independent functions wi= ll=20 be called. Maybe function A will call function B, or C will call A, whic= h=20 will then call B. Because of this, there are only two options I see for=20 local variables: 1) Use a data stack for all local variables 2) Allocate space for all local variables on the heap at run-time. This=20 means you will be using data space for every local variable in every func= tion=20 all the time, whether that function is running or not. I think I had a=20 routine that would implement a data stack on the PICs in the code, althou= gh=20 I'm not sure. So that data stack is not the problem. The problem is that the code st= ack=20 is either limited to the hardware stack, or you have to do an incredible=20 amount of work to get around it and implement it in software. With the P= ICs,=20 this is very difficult, which is why no one has done it. With the AVRs, = it=20 looks much, much easier. All the work I did on the original version was centered around the PIC=20 line, but seeing the AVR datasheets makes the PICs seem very old-fashione= d. =20 I would still like to support the PICs, I'm just not sure they will ever = be=20 able to do what the AVRs can. Where do you get your chips? The major sources for amateur electronics= I=20 have found are Digikey, Mouser, and Jameco. Digikey now sells several of= the=20 AVR (two pages worth), including some with no RAM or EEPROM for $2. Thos= e=20 might be interesting to implement a virtual machine on eventually... > The AVR line sounds pretty good for compilers. I wonder if they had > compilers in mind when they were designed. Perhaps to act more like > regular computers. I don't want to only support the AVR line though, > especially since I don't even know if I can easily aquire them > locally without special ordering them. The PIC is a popular chip, > and having a free compiler for it couldn't hurt at all. :) I didn't > look at the datasheets for the AVR chips. I suppose they support > 20MHz as well? That was the only question I had about them. Perhaps > I should take a look when thinking about these memory allocation > issues. I think I read on the Atmel site that the AVRs were designed with C=20 compilers in mind... that's why they have 32 general-purpose registers. = I=20 have not done optimization work, but I can see how 32 GP registers would = make=20 optimization much more efficient. They are rated at 4 or 8 Mhz, but they= are=20 designed like the Scenix chips, which means many of the instructions are = 1=20 instruction per clock cycle. The PICs use the traditional method which=20 requires 4 clock cycles per instruction. So actually the AVRs should be=20 faster than the PICs at top speed. If you count the reduction in overhea= d=20 for the data stack and the 32 GP registers, I guess the AVRs should be 2-= 5=20 times faster for C code. Did you say you are in Canada? I'm not sure where Digikey sells to, bu= t I=20 imagine you can get them through Digikey. They are a little high priced,= but=20 the service is excellent (fast delivery and phone help if you need it). Digikey is www.digikey.com and Atmel is www.atmel.com. |
|
From: Patrick E. <pa...@pa...> - 2001-07-19 08:24:07
|
On Wednesday 18 July 2001 12:49, you wrote: > > I would be interested in making it possible to work with both > > situations. I imagine it would be possible to do with some sort > > of generic variable request system. If you need a variable, you > > ask it for code to get to that variable. It decides if it's > > going to be local or global in scope based on if the processor > > supports local variables/recursion. I haven't thought about it > > that much yet. > > I think you may be getting two different things confused, or else > I don't understand what you're saying. Since the PICs have > separate data and code memory, there are separate data and code > stacks. You can still implement a data stack (up to 256 bytes) > with the PICs. In fact, I really don't see any other way to make a > proper C compiler except to use a data stack. The reason is: the > compiler has no way to know what way the independent functions will > be called. Maybe function A will call function B, or C will call > A, which will then call B. Because of this, there are only two > options I see for local variables: > 1) Use a data stack for all local variables > 2) Allocate space for all local variables on the heap at run-time. > This means you will be using data space for every local variable in > every function all the time, whether that function is running or > not. I think I had a routine that would implement a data stack on > the PICs in the code, although I'm not sure. With the PIC16F877, the data memory is fragmented. It you look on page 13 of the pdf for it, you can see that the largest unfragmented section is 112 bytes. Using the FSR and INDF alone, you can access 176 actual bytes of data memory. The full amount of memory is 386 bytes and can be accessed with the FSR and the IRP bit of the STATUS register. The stack will have to know when it's going to hit a boundary in order to jump to the next section. Alternatively, variables could be pre-allocated in order that you don't have to worry about hitting the end of the stack space. It's probably possible to build some sort of psuedo-stack-machine in the compiler that will deal with this fragmented data memory issue. > So that data stack is not the problem. The problem is that the > code stack is either limited to the hardware stack, or you have to > do an incredible amount of work to get around it and implement it > in software. With the PICs, this is very difficult, which is why > no one has done it. With the AVRs, it looks much, much easier. It's possible to do, but I doubt it would be worth it. With the chips not natively supporting it, it would be pretty lame to generate a slow software solution when a better idea would be for the programmer to rewrite their code to not use recursion. Recursion certainly isn't a requirement, and probably wouldn't help with 99.5% of the appplications of the PIC. Limited recursion using the hardware stack is possible on the 877, since it has 8 levels of stack. I'm more worried about the data issues than the difficulties with the hardware stack. > All the work I did on the original version was centered around > the PIC line, but seeing the AVR datasheets makes the PICs seem > very old-fashioned. I would still like to support the PICs, I'm > just not sure they will ever be able to do what the AVRs can. > > Where do you get your chips? The major sources for amateur > electronics I have found are Digikey, Mouser, and Jameco. Digikey > now sells several of the AVR (two pages worth), including some with > no RAM or EEPROM for $2. Those might be interesting to implement a > virtual machine on eventually... I get my chips at Active Components. It's a division of the company that runs www.future-active.com. It's a local store... I generally just drive over and pick up the parts I want. They happen to stock the 877 and the 84, so it makes it easy for me to acquire them. I could always special order things, but that's another step. > I think I read on the Atmel site that the AVRs were designed with > C compilers in mind... that's why they have 32 general-purpose > registers. I have not done optimization work, but I can see how 32 > GP registers would make optimization much more efficient. They are > rated at 4 or 8 Mhz, but they are designed like the Scenix chips, > which means many of the instructions are 1 instruction per clock > cycle. The PICs use the traditional method which requires 4 clock > cycles per instruction. So actually the AVRs should be faster than > the PICs at top speed. If you count the reduction in overhead for > the data stack and the 32 GP registers, I guess the AVRs should be > 2-5 times faster for C code. One issue is that I just got my PIC programmer to work under Linux. It took me a while to find something that would work to program the PIC16F877 under Linux. I spent more than a week unsucessfully trying to program the PIC, until I finally had success with the NOPPP programmer and the 16F84, which then required some hardware and software adjustments to work with the 877. If you want, you can read about what I did at http://patearl.net/pic_html I'm not in much of a hurry to build another programmer and buy more chips. I don't have a lot of money at the moment, as I'm saving up to buy a welder with my friend. That said, the AVR chips sound quite delightful, and under other circumstances, I'd probably jump at the opportunity to use them. As for now though, getting the PIC to work nicely is, to me, a fun challenge. I enjoy taking limited resources and making them work well. I've been studying the output from the compiler. It's pretty icky in terms of speed. I don't even understand parts of it. I still need to read more of it, but I'll probably have some questions for you, if you think you can answer them. > Did you say you are in Canada? I'm not sure where Digikey sells > to, but I imagine you can get them through Digikey. They are a > little high priced, but the service is excellent (fast delivery and > phone help if you need it). > > Digikey is www.digikey.com and Atmel is www.atmel.com. Ya, I'm in Canada. I'll have to try ordering from DigiKey sometime. I keep hearing about them. Look forward to hearing from you once again. Patrick Earl |
|
From: Daniel W. <dan...@ro...> - 2001-07-20 07:19:26
|
> With the PIC16F877, the data memory is fragmented. It you look on > page 13 of the pdf for it, you can see that the largest unfragmented > section is 112 bytes. Using the FSR and INDF alone, you can access > 176 actual bytes of data memory. The full amount of memory is 386 > bytes and can be accessed with the FSR and the IRP bit of the STATUS > register. The stack will have to know when it's going to hit a > boundary in order to jump to the next section. Alternatively, > variables could be pre-allocated in order that you don't have to > worry about hitting the end of the stack space. It's probably > possible to build some sort of psuedo-stack-machine in the compiler > that will deal with this fragmented data memory issue. Oh, ok. I didn't realize it was over 256 bytes. That explains why the= =20 data stack would also have some overhead. I still think that pre-allocat= ing=20 memory for local variables is a bad idea, unless the program doesn't use = much=20 of the available memory (in which case, you should be buying a cheaper mo= del=20 of PIC, right?). Also, the easy way to parse expressions is on the stack= =2E =20 I'm not really sure how I would do expression parsing without a stack. =20 > Limited recursion using the hardware stack is possible on the 877, > since it has 8 levels of stack. I'm more worried about the data > issues than the difficulties with the hardware stack. Now I see what you mean... I don't think the original PIC architecture = was=20 ever designed with the idea of having more than 256 bytes of memory. =20 Obviously they have just taken the old core and tacked new things on top.= =20 Kind of like the 8086 processor line. > I get my chips at Active Components. It's a division of the company > that runs www.future-active.com. It's a local store... I generally > just drive over and pick up the parts I want. They happen to stock > the 877 and the 84, so it makes it easy for me to acquire them. I > could always special order things, but that's another step. There is a nice electronics store down the street from me, but I'm not = sure=20 what microcontrollers they carry. I used to live in Fayetteville, Arkans= as,=20 which has about zero chance of anyone carrying microcontrollers locally. > One issue is that I just got my PIC programmer to work under Linux. > It took me a while to find something that would work to program the > PIC16F877 under Linux. I spent more than a week unsucessfully trying > to program the PIC, until I finally had success with the NOPPP > programmer and the 16F84, which then required some hardware and > software adjustments to work with the 877. If you want, you can read > about what I did at http://patearl.net/pic_html > > I'm not in much of a hurry to build another programmer and buy more > chips. I don't have a lot of money at the moment, as I'm saving up > to buy a welder with my friend. Yikes. So far I haven't even programmed any chips, despite the fact th= at I=20 built a programmer from a kit several years ago. I worked with the 68HC1= 1=20 when I was doing microcontroller stuff at Los Alamos for my research, and= it=20 was an evaluation board that was pretty much ready to go. I suspected th= at=20 actually getting PIC programming to work might be difficult, which is why= I=20 put it off. > That said, the AVR chips sound quite delightful, and under other > circumstances, I'd probably jump at the opportunity to use them. As > for now though, getting the PIC to work nicely is, to me, a fun > challenge. I enjoy taking limited resources and making them work > well. That was the main reason I started the project in the first place. It = is=20 definetly a challenge to get such a simple processor to run C code with=20 floating-point and all. There are a lot of cool things I would like to d= o=20 with it too. > I've been studying the output from the compiler. It's pretty icky in > terms of speed. I don't even understand parts of it. I still need > to read more of it, but I'll probably have some questions for you, if > you think you can answer them. You mean the compiler is slow or the generated code would run slow on t= he=20 PIC? The compiler if for sure slow... my symbol table isn't even a hash=20 table, it's a linked list that has to search the whole thing for each sym= bol=20 lookup! Obviously this will need to be changed eventually. I didn't do = that=20 originally because I didn't want to write a hash table. Now that I have=20 learned about glib this will be much easier. I am going on vacation starting Saturday morning until next Saturday or= =20 Sunday. Since my girlfriend isn't going with me, I will print out the co= de=20 and look at it when I'm recovering from the hikes. Hopefully then I will= be=20 up to speed again about how it works, so I can start a developers documen= t=20 with Lyx and be able to answer question better. |
|
From: Patrick E. <pa...@pa...> - 2001-07-21 00:25:21
|
On Friday 20 July 2001 00:21, you wrote:
> I am going on vacation starting Saturday morning until next
> Saturday or Sunday. Since my girlfriend isn't going with me, I
> will print out the code and look at it when I'm recovering from the
> hikes. Hopefully then I will be up to speed again about how it
> works, so I can start a developers document with Lyx and be able to
> answer question better.
I'll have to write more about what I was talking about. I didn't
really explain my thoughts very well. I'm sure I'll have more ideas
by the time you come back. I'm going on a little trip myself at the
moment. It's only until tommorrow though. I'll try to write some
detailed replies to your messages soon. Have a good trip! :)
Patrick Earl
|
Thanks for helping keep SourceForge clean.
X