Determining the maximum stack depth

Question

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.

Answer 1

Given that your language doesn't seem to have any user input all programs will simply compute in the same way all the time. Therefore, you could execute the program and keep track of the maximum stacksize during execution. Probably not what you want though.

As for your path argumentation: Be aware, that jumping allows cycles, hence, without further analysis a cycle might imply non-termination and stack overflows (i.e. stack size is increased after each cycle execution). [n nodes still means infinitely many paths if there is a cycle]

Instead of actual execution of the code you might be able to do some form of abstract interpretation.

Regarding the comment from IVlad: Simply counting the pushs is wrong due to the existence of possible cycles.

I am not sure what the semantics of your if-statements is though, so this could be useful too: Assume that an if-statement's label can only be a forward label (i.e., you can never jump back in your code). In that case your path counting argument comes back to life. In effect, the resulting CFG will be a tree (or DAG if you don't copy code). In that case you could do an approximative count, by a bottom-up computation of the number of pushs and then taking the maximum number of pushs for both branches in case of an if-statement. It's still not the optimal correct result, but yields a better approximation than a simple count of push-statements.

Answer 2

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.