# REP7: EFA4 **Status**: `✅ DONE` ## Goals EFA4 marks, for each function, a set of registers as arguments of the function and another set of registers as return values of a function. **Goal #1**: for each function, EFA produces sets of registers that are the minimal set of registers required to ensure that the following two assumptions hold. **Assumption #1**: there are no uninitialized reads from registers. **Assumption #2**: there are no dead writes to registers. We have two analyses: a liveness analysis and a reaching definition analysis. ## Liveness Analysis The liveness analysis tells us about what registers are arguments of a function and return values of a call site. The core idea is that, if a register is *alive* at the entry of the function, it either has one or more uninitialized reads *or* the register is actually an argument. Similarly, if a register is *alive* after a function call that does not preserve it, it either has one or more uninitialized reads *or* the register is actually a return value of the call site. As per assumption #1, we choose to say that in the former case it's an argument of the function and in the latter case it's a return value of the called function. ### Analysis definition **Starting point**: all exit nodes. TODO: What do about infinite loops? **Direction**: backward. **Object of analysis**: registers. **Lattice**: partset of the set of registers. Combine is set union. **Transfer function**: `read x` adds `x` to the set, `write x` removes `x` from the set. **Results collection**: collect the set of registers alive at the entry point, they are the arguments of the function. Similarly for return values of a call site (`postcall_hook`). ## Reaching definitions The reaching definitions analysis will tell us about what registers are return values of a function and arguments of a call site. In general, the reaching definition analysis tells us, for each instruction reading a register, by which instruction writing it, it might be affected. This analysis can be used to implement a dead store elimination transformation: if an instruction writing a register does not reach any read of such register, it is dead. Under assumption #2, we can say that all the instructions that seem to be performing a write to a register that no other instruction reads, is actually setting the return value. The core idea of the analysis is to collect at the exit point the set of reaching definitions that are not reaching any other instruction performing a register read. The registers written by such instructions are return values. Similarly, the set of instructions that reach a call site that does not preserve the written register and reaches no other read instruction, are considered arguments of the called function. ### Analysis definition **Starting point**: entry node. **Direction**: forward. **Object of analysis**: instructions writing a register. **Lattice**: partset of the set of instructions writing a register. Combine is set union. **Transfer function**: `write x` removes all the other instructions writing `x` from the set and introduces in the set the current instruction. **Results collection**: 1) Iterate over all the program points reading a register and accumulate in a set `Read` the analysis result. 2) Combine the results of all proper return points and subtract `Read`. The result is the set of return registers. Similarly for arguments of a call site. ## Interprocedural instrumentation We need to inject in the function "virtual reads" for each register known to be an argument of a call site and for each register known to be a return value of a function. We do not need to inject writes for arguments of the function and for return values of a function, because those would only increment the set of registers and violate goal #1. On the other hand, not injecting the virtual reads, would lead to violations of assumption #1. In order to persuade yourself that this makes sense consider the following example: ```graphviz digraph { node [shape=box]; main -> wrapper -> getenv } ``` Let's assume the prototype of `getenv` is well known, `wrapper` is a simple wrapper called by `main`. Injecting a virtual read before the call site targeting `getenv` in the `wrapper` function, will lead to propagate the arguments of `getenv` to `wrapper` *but not* the return value! If we wanted to propagate the return value too, we should inject a write to the return register after the call site. However, it's possible that the call site ignores the return value. And, in order to be coherent with goal #1, we don't want to do that. However, if `main`, after the call to `wrapper`, has an uninitialized read from `rax`, a clear contradiction of assumption #1, this will lead `wrapper` to have `rax`. ## Open questions * For the reaching definitions, which is backward, how do we keep into account infinite loops that do not reach the exit? Force the MFP to run over all nodes. * Do we need to handle in some special ways `TheCall`? No. * What about weak writes? We need to consider weak writes in the reaching definitions so that, they remove similar stores from the set, *but* do not add themslves.