English
资源说明：Stacker is a static analysis tool for analyzing the amount of stack space used by a program.
Stacker ======= In small embedded systems, memory is generally a very scarce resource. Most memory usage can be controlled and checked at compile time, by avoiding ``malloc()`` and instead using fixed-size values in .bss. If a dynamic allocator is used, it is difficult to predict how much memory is "actually necessary", but code can detect when an allocation fails due to lack of memory and act accordingly. The one remaining way memory can be used is on the stack. Local variables that cannot fit in registers and saved state around function calls are all placed on the stack in a stack frame produced by each function on entry and removed on exit. The stack is, in some sense, another general-purpose memory allocator: allocation is performed by calling a function, and memory is freed when the function that calls it returns. Some constructs in C allow arbitrary amounts of memory to be alocated on the stack, determined at runtime. Local variables in a recursive function are instantiated for every call to that function, and there can be any number of such calls. The ``alloca()`` function and variable-length arrays (standard in C99 and supported in many earlier compilers) can change the size of a stack frame at runtime. Clearly, it is not possible to write a tool to accurately bound the stack usage of *any* C program; this is prohibited by the implications of Rice's theorem and the *Entscheidungsproblem*. Fortunately, a few restrictions allow us to avoid undecidability. A program in most procedural languages like C can be viewed as a graph of functions: each function has an edge to every other function that it might possibly call. We make the assumption that every call not optimized away by the compiler is a call that might happen at runtime. The *call graph* starts at the first function executed by the program. If the call graph is cyclic, the program might recurse; otherwise, every possible call path can be enumerated and analyzed separately. Function Analysis ----------------- A very simple compiled function has a structure something like: * Allocate some space on the stack * Perform computation, possibly calling other functions * Free the allocated stack space * Return In practice, this is complicated in several ways. Allocating stack space is performed along with saving call-saved registers using "push" instructions, as well as by manipulating the stack pointer directly, and (on some architectures) also during "call" instructions; freeing of space happens through several mechanisms as well. To improve performance at the expense of code size, compilers may duplicate parts of the end of a function's code, so a function may have many return sites. Finally, some function calls are implemented by the compiler as "tail calls": they occur *after* a function's stack frame has been freed. (Tail call optimization was developed to allow recursive functions to be compiled efficiently, but it helps reduce stack usage even in non-recursive programs.) Stacker analyzes functions by first parsing the assembly produced by the compiler and identifying function names and boundaries. Then, instructions are translated into a machine-independent form, and instructions not relevant to inter-function control flow or stack usage are filtered out. This turns a function into a stream of pseudo-operations like "change stack usage" (specified with a positive or negative delta), "call", "tail-call", etc. Then, Stacker parses these sequences against its understanding of function idioms produced by compilers, like return site duplication. Each function is reduced to a number of bytes of stack usage, a set of possible callees, and a set of possible tail-callees. At this point, Stacker can assemble the call graphs in the program, and find the total stack space used by the longest such path.
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
