(I was planning to make it a comment but it turned out rather long and it makes an answer on its own)
Some of the comments mentioned the Hex-Rays decompiler. Its basic ideas are not a trade secret and are in fact described in the white paper by Ilfak Guilfanov which accompanies the presentation he gave in 2008.
I'll paste the relevant part here:
Local variable allocation
This phase uses the data flow analysis to connect registers from different basic blocks in order to convert
them into local variables. If a register is defined by a block and
used by another, then we will create a local variable covering both
the definition and the use. In other words, a local variable consists
of all definitions and all uses that can be connected together. While
the basic idea is simple, things get complicated because of
It's simple on the surface but of course the implementation has to account for numerous details. And there's always room for improvement. There's this passage:
For the time being, we do not analyze live ranges of stack variables
(this requires first a good alias analysis: we have to be able to
prove that a stack variable is not modified between two locations). I
doubt that a full fledged live range analysis will be available for
stack variables in the near future.
So, for stack variables the approach right now is simple: each stack slot is considered a single variable for the whole function (with some minor exceptions). The decompiler relies here on the work done by IDA during disassembly, where a stack slot is created for each access by an instruction.
One current issue is multiple names for the same variable. For example, the compiler may cache the stack var in a register, pass it to some function, then later reload it into another register. The decompiler has to be pessimistic here. If we can't prove that the same location contains the same value at two points in time, we can't merge the variables. For example, any time the code passes an address of a variable to a call, the decompiler has to assume the call may spoil anything after that address. So even though the register still contains the same value as the stack var, we can't be 100% certain. Thus the excess of variable names. User can override it with manual mapping, however.
There are some ideas about introducing function annotations that would specify exactly how a function uses and/or changes its arguments (similar to Microsoft's SAL) which would alleviate this problem, but there are some technical implementation issues there.