# Determining the maximum stack depth

Posted
by Joa Ebert
on Stack Overflow
See other posts from Stack Overflow
or by Joa Ebert

Published on 2010-05-03T09:52:12Z
Indexed on
2010/05/03
10:18 UTC

Read the original article
Hit count: 375

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?

© Stack Overflow or respective owner