3. The GNATstack Tool

The GNATstack tool statically computes the maximum stack space required by every stack entry point (including tasks) in an application. The computed bounds can be used to ensure that sufficient space is reserved, thus guaranteeing safe execution with respect to stack usage. The tool uses a conservative analysis to deal with complexities such as subprogram recursion, while avoiding unnecessarily pessimistic estimates.

This static stack analysis tool exploits data generated by the compiler to compute worst-case stack requirements. It performs per-subprogram stack consumption computation combined with control flow analysis.

This is a static tool in the sense that its computation is based on information known at compile time. It implies that when the tool indicates that the result is accurate then the computed bound can never overflow. The tool does not rely on empirical run-time information.

The main output of the tool is the worst-case stack requirements for every entry point, together with the paths that lead to these stack needs. The list of entry points can be automatically computed (all the tasks, including the environment task) or can be specified by the user (a list of entry points or all the subprograms matching a certain regular expression).

Note that if the linker performs a partial link (this is the case of VxWorks targets, excluding RTP mode in VxWorks 6) then the main entry point will need to be specified using the -e option (see Options for GNATstack).

GNATstack also generates a Visualization of Compiler Graphs (VCG) file containing the complete call tree for the application, decorated with both local and accumulated stack usage information. The VCG graph description language is used in GCC for other graph outputs.

Apart from the computation of worst-case stack requirements, GNATstack can also perform four additional types of analysis:

• Indirect (including dispatching) calls. The tool indicates the number of indirect calls made from any subprogram.

• External calls. The tool displays all subprograms that are reachable from any entry point for which we do not have any stack or call graph information.

• Unbounded frames. The tool displays all subprograms that are reachable from any entry point with unbounded stack requirements. The required stack size depends on the arguments passed to the subprogram.

• Cycles. The tool can detect all cycles in the call graph. These cycles represent potential recursion and hence potentially unbounded stack consumption.

GNATstack aims at finding an upper-bound to stack usage by static analysis techniques that give accurate results if some conditions are met, such as no indirect calls, no variable-sized local variable, no recursion and full access to the complete environment (including run-time and system calls). These conditions, and in particular the last one, are not easy to meet completely using the full Ada run-time libraries. When all these conditions are not met, there is still interesting information that can be obtained about stack usage, but going all the way to find a reliable stack usage upper-bound may require a fair amount of manual work.

GNATstack provides the infrastructure to allow users to specify in a text file the missing information, such as the potential targets for indirect calls, stack requirements for externals calls, and user-defined bounds for unbounded frames.