One of the biggest problem of the memory use when you are in a resources limited target is the high cost of dynamic memory functions malloc and free. Dynamic memory is usually implement as a single or double linked list (double linked is faster but increment minimun size of allocated memory), and malloc runs over this list searching for a block with enough size for the request memory, and free inserts the block which contains the memory into the list (and joins to next or previous block if they are contiguous). These operations are very slow.
Other solution is using alloca function, which returns a pointer to allocated memory into the stack, that can be implemented with only a pair of instruction and has the advantage that memory is freeded automatically when function returns. But alloca has problems too:
- Doesn't check for memory bounds.
- Due to the use of stack is very dangerous uses it as parameter of a function
- It is compiler and machine depend and it is not part of ANSI C or C99.
I think problem 1 is not important because there isn't way of checking correctness of a stacked array too. For example:
char vector[30];
is equivalent to
char * vector = alloca(30);
And there isn't way of checking stack overflow in recursive functions (at least in a portable way of course). And even in C99 exists dynamic arrays:
void function(size_t val)
{
char vector[val];
...
}
So although alloca can be dangerous due to it doesn't test limit, it is safe when we can assume small sizes. Typical use is getting a path name.
In the other hand although isn't standard it is supplied by almost compilers and there is a portable implementation (but less efficient because it uses heap memory).
So alloca is a desirable function for a limited resource environment as Z80. After looking for it in documentation of my compiler (Hitech C) I saw that it didn't have it, so I had to implement it. The first problem that I had to solve was I needed an inline implementation, but I didn't have the sources of the compiler. Some time ago I did a small perl script which did some peephole optimizations to the assembler code generated with the option -S, and I saw that solution could come thanks to this optimizer. A inline substitution wasn't different of a peephole optimization.
In first step I wrote alloca.h header:
#ifndef __ALLOCA_H__
#define __ALLOCA_H__
#ifndef _STDDEF
typedef unsigned size_t;
#endif
/*
Be aware of using push/pop and alloca in the same function
due to this can cause a stack corruption.
*/
void * alloca(size_t size);
unsigned push(unsigned val);
unsigned pop(void);
#ifndef _DEBUG_ALLOCA
#define push(val) _builtin_push(val)
#define pop _builtin_pop
#define alloca(val) _builtin_alloca(val)
void * _builtin_alloca(size_t size);
unsigned _builtin_push(unsigned val);
unsigned _builtin_pop(void);
#endif /* debug */
#endif /* __ALLOCA_H__ */
I inserted two inlined functions more (push and pop that I will explain them later). So with this macro substitution I added a new peephole optimization in my perl script:
#change __builtin_push, __builtin_pop and __builtin_alloca by assembler instruction
#push
s{
\tcall\t__builtin_push\n #call __builtin_push
}[\tex\tde,hl
\tpush\thl
]gx;
s{
\tglobal\t__builtin_push\n
\tsignat\t__builtin_push,.*\n
}[
]gx;
#pop
s{
\tcall\t__builtin_pop\n #call __builtin_pop
}[\tpop\thl
]gx;
s{
\tglobal\t__builtin_pop\n
\tsignat\t__builtin_pop,.*\n
}[
]gx;
#alloca
s{
\tcall\t__builtin_alloca\n #call __builtin_alloca
}[\tld\thl,0
\tadd\thl,sp
\tsbc\thl,de
\tld\tsp,hl
]gx;
s{
\tglobal\t__builtin_alloca\n
\tsignat\t__builtin_alloca,.*\n
}[
]gx;
With these perl regular expressions we already have done it. For each inlined function we need delete global and signal declarations because in other case the assembler will fail. Due to the compiler thinks he is calling to a real function it stores first parameter in de register (binary protocol used by this compiler) and allows modify all register except iy, so in alloca case we only need decrement stack pointer.
The other 2 functions, push and pop, are used to implement a very, very optimized stack in the z80 stack, for example for a search algorithm.
