Q:

Register Allocation and Definition of Interference

In my textbook on compiler design [1], it describes interference between two variables (the property that they cannot be in the same register at once) as follows:

Definition 9.2:  A variable $x$ interferes with a variable $y$ if $x \neq y$ and there is an instruction $i$ such that $x \in kill[i], y \in out[i]$ and instruction $i$ is not "$x := y$"

This definition does not make sense to me. If I interpret this in plain English:

A variable interferes with another if some variable $x$ is being overwritten, while some variable $y$ is live at the exit of the instruction, and the instruction is not $x := y$ and $x$ and $y$ have distinct values.

To me, a more logical definition of interference is if two variables $x$ and $y$ appear in the same $gen$ set of some instruction $i$. This necessarily means that these two variables are used (i.e their value) in the same instruction. Is there some crucial detail that I am missing?
For those interested, this definition appears on page 197 of the book referenced above.

A:

Your "reading" of the definition is a little unclear. In particular, it says nothing about the values of the variables. Here's a clearer reading:

A variable $x$ interferes with a variable $y$ if 1) they are not the
  same variable, i.e. a variable never interferes with itself, and 2) there
  is some instruction other than $x := y$ where $x$ is overwritten while
  $y$ is live at the end of the instruction (and typically also
  during, but a multiple assignment instruction like $(x,y):=(a,b)$ would be an example where variables can interfere even though $y$ is not live during the instruction).

As the book points out immediately after that definition, if $x$ and $y$ have the same value (for some stretch of code), then there is no reason they can't be held in the same register (in that stretch of code). This is what makes ignoring $x := y$ instructions valid. The analysis does not calculate the values of anything however. $x$ and $y$ interfere in $\{x := k;y := k; f(x,y)\}$ and so will be assigned different registers. For this analysis to exploit the fact that they have the same value, a prior optimization pass would need to rewrite it to $\{x := k; y := x; f(x,y)\}$.
Your definition is also incorrect. The $gen$ set of $x := k$ is empty, but certainly two variables can't share a register if one is being mutated and the other isn't. Again, as the book points out immediately after the definition, the definition is close to saying that distinct variables $x$ and $y$ can't both be live at the same time. (Both being live at the same time would be formulated as $x,y \in out[i]$.) This is a more conservative condition than yours, but it is still incorrect for the same reason. If $x := k$ is the last occurrence of $x$, and thus isn't in the $out$ set of that instruction, it still interferes with $y$.

