I was wondering if any developers in the embedded space know of any interesting tricks to help lessen the pain of developing for microcontrollers with very limited stack space. I've recently been writing some firmware for 8-bit uCs (Microchip PIC18F family, 31 byte stack) and as a consequence I have had to flatten my programs and reduce the number of parameters passed to functions. I've also tried to minimize my dependence on larger local variables. The flattening was designed to put fewer things on the stack and reducing locals variables helps conserve space in the "automatic variable" program section (psect) in RAM. Harvard architecture is not fun, I know, but it is what I'm dealing with. I've noticed issues with calling more than a few functions deep from an ISR, which is probably the result of my stack window being affected by IRQ context saving. I know I'm working with a limiting architecture, but I wonder if anyone has any tips for reducing headaches. I use pointers and bounds checking whenever possible, but I'm sure there are nuggets of wisdom I haven't discovered myself. As a disclaimer, I'm currently using function pointers to facilitate a state machine. I feel like I'm walking a tightrope between 90 line void functions and code that actually uses functions as they are intended.
Use register variables for parameters and locals. Of course, depending on the number of registers available in the processor and the quality of the code the compiler generates, this may be no benefit at all. Declare locals as static where possible. This will keep them from being allocated on the stack.
Use a whole-program optimizing compiler that can effectively statically allocate the "stack" -- I believe the Hi-Tech PICC compilers can do this. See section 5.9 in the PICC18 manual
Use protothreads
Use non-local goto (setjmp() and longjmp(), with the jmp_buf not stored on the stack) to avoid function calls.
For non-recursive functions, you can make your local variables static.
BTW, the term "Harvard architecture" simply refers to the fact that there are separate address spaces for instructions and data, as opposed to a "Von Neumann architecture" that loads instructions from the same address space that data comes from. This is irrelevant to your problem, as all it means is that you can't write self-modifying code.
EDIT
The PIC family is not a compiler friendly instruction set architecture. The first trick for dealing with the small stack and in general limited resources on a PIC is to program in assembler. You can perform more tasks in the same program space and same execution time or same task in less time than programming in C.
The second is just dont use the stack. Make your variables globals or local globals (local variables with the word static in front), whatever you call it or however you declare it the compiler output is the same the variable has one static memory location and does not use the stack.
For processors other than the PIC family you can use an optimizer or register declaration of variables to prevent use of the stack. The PIC has only two registers and to do anything useful you have to constantly evict the contents to ram, so this will have a minimal effect on the PIC. For non-PIC processors, in addition to encouraging the compiler to retain the data in registers as much as possible, you can aid in that by limiting the number of variables passed into the function as well as the number of additional local variables used by the function. For cases where it is not obvious how many registers are used, disassemble and examine the compiler output, re-arranging your code execution can change the register allocation and eviction. If that does not work consider splitting the function into two and calling one then the other in turn, such that each function is able to execute within the available registers without using the stack.
If this project is for a fun educational experience then programming for the PIC is educational in and of itself, and programming the PIC in C is also an educational experience. Well worth learning, well worth falling into traps and fighting your way back out.
If you are doing this for work (career and/or livelihood hangs in the balance) and do not want to program in assembler, I recommend trying to switch the project to another platform. msp430, avr, or one of the ARM based ones (stellaris perhaps). Knowing ARM is very beneficial to your career in embedded, but the ARM parts are going to be a bit bulkier from a power and cost perspective compared to a PIC. The avr and msp430 parts are more on par. All three of these alternate architectures are much more suited to C programming and the same program will consume less memory/stack than the equivalent on the PIC. Meaning you may be able to replace say an 8K PIC with an 8K something else, you wont necessarily need more memory on the alternate architecture in order to do more. You still have to worry about your stack, and should avoid (non-global) local variables to prevent stack growth. These architectures also vary from the PIC by not having a separate stack and general purpose ram. You are free to balance globally allocated variables and stack based variables and not forced by the architecture. If stack based variables are used, in a work environment, review the code to determine the worst case path of nested functions and count how many non-global variables are in that path and if that causes the stack to collide with the globally allocated variables.
Disassembly is your best friend in embedded, you dont necessarily have to program in assembler but should still be able to read it. Examining the assembly is the best trick of all for reducing all forms of embedded pain: stack problems, memory usage, performance, bootup problems, etc.
I was once programming for 8051 and we were using the Keil C compiler for doing that. This compiler didn't call functions by using the stack but by transferring parameters using global functions (you could still get this behavior by marking the function "reentrant"). I think it also did reduce stack usage by doing some more stuff.
What I want to say is that there are compilers that will use less stack space than others. If there are such compilers available for PIC, I can't tell.