I was thinking something similar: how does Prepack determine that a function can't be optimized or hits an infinite loop? Seems like the good ol Halting Problem[0].
The Halting Problem is a bit like Information Theory.
Information Theory, and the Pigeon Hole Principle in specific, says there is no algorithm that can compress all data. That doesn't mean that compression is a fruitless endeavor and we should never have written a compression library.
It means that you have to figure out if your input falls into a subset of data where the outcome of the effort is both tractable and useful. You compress text and structured data, you don't compress noisy data or already compressed data, because it's usually worse than doing nothing.
Similar thing with code analysis. If there is back branching or asynchronous code, you are probably going to hit the Halting Problem, so don't even try. But if the code is linear, then precomputing the output is tractable and useful.
You could also simply apply a budget. If an attempt to unroll a block of code exceeds a certain number of clock cycles or branch operations, you should give up and look at the next most likely scenario. The analysis you're doing might reliably halt in an hour, but who wants to wait that long? Especially when it's one of many such evaluations you'll have to do per build or per day? Just give up and keep moving.
Information Theory, and the Pigeon Hole Principle in specific, says there is no algorithm that can compress all data. That doesn't mean that compression is a fruitless endeavor and we should never have written a compression library.
It means that you have to figure out if your input falls into a subset of data where the outcome of the effort is both tractable and useful. You compress text and structured data, you don't compress noisy data or already compressed data, because it's usually worse than doing nothing.
Similar thing with code analysis. If there is back branching or asynchronous code, you are probably going to hit the Halting Problem, so don't even try. But if the code is linear, then precomputing the output is tractable and useful.
You could also simply apply a budget. If an attempt to unroll a block of code exceeds a certain number of clock cycles or branch operations, you should give up and look at the next most likely scenario. The analysis you're doing might reliably halt in an hour, but who wants to wait that long? Especially when it's one of many such evaluations you'll have to do per build or per day? Just give up and keep moving.