Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That looks to me like an NP complete problem.


Not if the set of answers includes "couldn't determine an upper bound".

Many (but not all) problems become a whole lot easier if you restrict them to sane inputs. Determining an upper bound on stack size is especially interesting for, e.g., embedded software, and the intersection of "sane embedded program" and "program with complex stack size behavior" is rather small.


Specifically if features like function pointers are avoided, and tail call optimized recursive data structure functions are used. Hell for embedded uses if it can just determine it for some functions, and not others (like say anything involving dispatch) it would still be very useful.

From writing:

    TaskCreate(&some_func, 2048 /* Hope this is enough stack */)
To:

    TaskCreate(&some_func, sizeof(some_func))
would be amazing.


Original Fortran compilers were able to tell exactly how much stack any program was using. The answer was zero as all local variables were allocated statically and recursive calls were not supported.

But one does not need to go to such extreme as many useful code patterns can be proven to be stack bounded and for the rest of code the compiler may require runtime checks or some annotations like Rust’s unsafe.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: