Well, the overzealous stack allocation problem in my program is likely due to inline functions, because it can be fixed by disallowing them using -fno-inline. This causes the stack frame of my interpret function to shrink to 12 bytes from 44.
This is really quite horrible, because the functions I declared inline used no local variables. It's possible that gcc was inlining larger functions, so I'll have to check into that. What I'm reading indicates that GCC has difficulty re-using stack space for multiple inlined functions. If so, that sucks.
I'm guessing the long term solution will be to only allow GCC to inline functions that I specify.
I did some searching and apparently I'm not the first one with this problem:
Linux and GCC inline
From Linus: "Gcc inlining is a total and utter pile of shit."
I'll take his word for it, but my experience bears this out. I guess I'll be using macros instead.