NCSDIS: Analyse control flow for recursive functions, and functions with incompatible fork merging about xoreos-tools HOT 1 OPEN

As discussed privately with @DrMcCoy and on DeadlyStream, I have a potential solution to the recursion issue. Copy/pasting my algorithm below:

*** BEGIN QUOTE ***
Hey so I've realized that this heuristic analysis [edit: this is referring to another algorithm I suggested, not the guessing one - I still suspect that might work] is not reliable enough to be used properly, but I came up with another solution which works every time. The problem is that the Skywing documentation is incorrect, and JSR does in fact work just like ACTION in that it modifies the stack pointer by popping off arguments. It doesn't push on a return value though (if there is one, space for that must have been allocated by the caller function before calling the callee). Perhaps what they mean is that the JSR does not do anything "intrinsically", but the function calling convention appears to be that functions pop their own arguments (which is more reasonable than making the caller do it every time; this is something I've actually taught before in computer science classes).

In any case, what you can do is the following (after constructing a call graph):
For each subroutine in the call-graph, iterating with DFS reverse post-order traversal:

1. If the current subroutine is part of a cycle in the call graph:
   1.a. Collect all the subroutines in the cycle
   1.b. Trace both the final stack pointer and subroutine calls from every possible path from the start block of each subroutine to a block with no successors.
   1.c. For each of these paths, we can form an entry in a system of simultaneous equations, where the final stack pointer is on the RHS and the subroutine calls are on the LHS. For example, if a path through subA calls subB 2 times and subC 2 times, and the final stack pointer is -8, our equation would be "0a + 4b + 2c = 8".
   1.d. Solve this (potentially overdetermined) system of linear equations for a, b, c, ... which are the number of arguments for subroutines A, B, C, ... respectively.
2. Otherwise, compute the number of arguments as per usual for non-recursive functions. Can then also determine if there's a return value after finding the number of arguments.

One issue with this is the problem of vector/struct arguments. This method will tell you the size of the stack space which is popped from the stack after calling each subroutine; however, it does not tell you the structure of said space. However, this is easy to calculate once you know the number of arguments - when you call the function in another subroutine, you can use the state of the stack at that call to determine the types of the sub's arguments (including how much space they take up).

*** END QUOTE ***

To be clear, even though the linear system might be overdetermined, it should still have only one solution. One easy way to implement this is to use a linear algebra solver for overdetermined systems, and check the residual is zero (within a tolerance).

I've implemented this algorithm in my ncs2nss repo if you're interested. It doesn't work all the time, but I suspect this is due to either bugs in the rest of my code (there are still many) or compiler errors. I feel the latter can be resolved with a modification to the algorithm, but we can discuss that later.

from xoreos-tools.