How can we determine how much memory is being used, or will be used by
firmware in a microcontroller? What tools can support this?
The static (compile-time) information can usually be found in an output file generated by the linker, if you request it. Most linkers will have an option for this purpose, as well as options to greatly expand the level of detail provided. You should look to the documentation on the linker tool for ways to generate these listings, expanded or simple. (I used to just call these "map files.")
When a compiler (or several different compiler front ends, if you use gnu tools and like to program in multiple source languages) generates object files, these need to be linked together with library code in order to produce the final result. That result will include all the code, all of the required initialized data, and all of the statically allocated data.
There are some dynamic (run-time) memory allocations (stack and heap, for example.) These will NOT be included in the linker's map output file, for obvious reasons.
Generally we don't use dynamic memory in embedded systems, but how can
we determine the worst case stack usage for example? A compiler can't
be enough.
Different people use different methods for testing and validating stack usage. A way that does not test for worst case (unless you get lucky) is to first set all of the available stack space to a "special value" prior to the main code starting up. Then you run it for a while, poke away at different features and functions within the software, and finally freeze things and go look at the memory. It's pretty easy to see how much got "stepped on" during execution.
If you want the actual "worst case," there are a couple of ways. One is to exhaustively test all of the code -- some medical (critical) software requires that every single line of code be tested. If you work out a testing regime to meet that requirement, you can probably work out the worst case (using the "special value" technique just mentioned and being exhaustive in testing.)
But some compiler tools (often at the linker stage but not always and, most notably, the ones written for the 8051 core because of some reasons of history and its design architecture; but I'm sure many others as well) offer the ability to build and then analyze the call graph in order to calculate the maximum stack usage. This static analysis works okay if your code doesn't make indirect calls using function pointers. So some compilers also allow you to provide them with a list of functions that might be called from each calling function in some kind of "stack usage control file" that you have to provide. So this is another possible way.
Of course, you can work it out by hand (given enough time and money, most things can be done.)
For example we may not know until run-time how many times a function
could be called, potentially causing a stack-overflow.
Yes. So see the above discussion I just provided.
can a debugger tell us exactly at any point in the execution flow, how
much memory is being used?
I'm not entirely sure what you mean. But perhaps you mean that if you hit some breakpoint, can the debugger tell you enough? It may be able to do so. Some hardware includes information that can be reported by the debugger that will tell you a lot. The stack pointer, for example, will have a value in it that tells you where the stack bottom is currently at. That can tell you the stack usage up to that point. (However, because activation frames may have been used and then freed before you get to your breakpoint, that might not be as helpful as you'd like. You might have picked a bad location for the breakpoint.)
Often, heap space information is also important. And there are tools that will walk the heap space for you and tell you what's in use, what's not in use, etc. You can also use heap allocation libraries that will report very detailed information on the heap space usage. You could include those libraries, while testing. For stack space, if your MCU supports segmented or paged memory allocation for the stack, then information can be captured and reported to tell you the worst case usage of the stack (so far.)
So what brought all these questions to the fore? If you have a specific compiler toolset, just ask the vendor. They will be able to provide you with all the details available to your circumstances. If you are just asking "in general," then the above is the best I can offer you, in general.
