stackstatic-analysiscompiler-theorycontrol-flow-graphstack-size# Determining the maximum stack depth

Imagine I have a stack-based toy language that comes with the operations Push, Pop, Jump and If.

I have a program and its input is the toy language. For instance I get the sequence

```
Push 1
Push 1
Pop
Pop
```

In that case the maximum stack would be 2. A more complicated example would use branches.

```
Push 1
Push true
If .success
Pop
Jump .continue
.success:
Push 1
Push 1
Pop
Pop
Pop
.continue:
```

In this case the maximum stack would be 3. However it is not possible to get the maximum stack by walking top to bottom as shown in this case since it would result in a stack-underflow error actually.

CFGs to the rescue you can build a graph and walk every possible path of the basic blocks you have. However since the number of paths can grow quickly for n vertices you get (n-1)! possible paths.

My current approach is to simplify the graph as much as possible and to have less possible paths. This works but I would consider it ugly. Is there a better (read: faster) way to attack this problem? I am fine if the algorithm produces a stack depth that is not optimal. If the correct stack size is m then my only constraint is that the result n is n >= m. Is there maybe a greedy algorithm available that would produce a good result here?

**Update:** I am aware of cycles and the invariant that all controlf flow merges have the same stack depth. I thought I write down a simple toy-like language to illustrate the issue. Basically I have a deterministic stack-based language (JVM bytecode), so each operation has a known stack-delta.

Please note that I do have a working solution to this problem that produces good results (simplified cfg) but I am looking for a better/faster approach.

Solution

You generally want to have the stack depth invariant over jumps and loops.

That means that for every node, every incoming edge should have the same stack depth. This simplifies walking the CFG significantly, because backedges can no longer change the stack depth of already calculated instructions.

This also is requirement for bounded stack depth. If not enforced, you will have increasing loops in your code.

Another thing you should consider is making the stack effect of all opcodes deterministic. An example of a nondeterministic opcode would be: POP IF TopOfStack == 0.

**Edit:**

If you do have a deterministic set of opcodes and the stack depth invariant, there is no need to visit every possible path of the program. It's enough to do a DFS/BFS through the CFG to determine the maximum stack depth. This can be done in linear time (depending on the amount of instructions), but not faster.

Evaluating if the basic blocks, at which the outgoing edges of your current basic block point, still need to be evaluated should not be performance relevant. Even in the worst case, every instruction is an `IF`

, there will be only 2*N edges to evaluate.

- How to print out all elements in a std::stack or std::queue conveniently?
- Leetcode Proble - 20. Valid Parentheses
- Register based VM - byte order - push/load
- How do I push the result on stack in a subroutine?
- How could you come to the intuition that Valid Parentheses on Leetcode requires a stack?
- Refused to apply inline style because it violates the following Content Security Policy
- I do not understand what exactly is dynamic memory allocation
- Understanding Postfix-expression Evaluation in Java code using a stack
- How can I add the time dimension to a series of .tif files?
- How is my algorithm for stock span problem incorrect?
- Problem with blurring a part of the widget
- Is there an efficient way to sort data only using stacks?
- Assembly code, printf and allocating space on the stack
- Determining the maximum stack depth
- Why do the 32-bit and 64-bit Compiled Versions of this Program Populate Memory in this Way?
- Unexpected behaviour when trying to implement a queue with two stacks in C
- Calling convention and stack, returning value from call?
- Do stacks have indexes?
- Turn my stack into a string?
- Push all and pop all in emu8086
- push_back operation in c# containers
- How to get function Argument from Stack - Assembly
- Fish codility excercise
- Overflowing a stack frame with 0x00001292 in C
- Codility : Brackets Determine whether a given string of parentheses is properly nested
- How do I read a struct contents in a running process?
- Increase Stack Size on Windows (GCC)
- What happens with the Frame Pointer in the Stack, if the Stack Pointer enters a second, nested function?
- Can we allocate Stack Memory at Runtime?
- boxplot two rasters and one shapefile