Consider this: Int32 @2 = Add(@1, @1) Ignoring for a moment the fact that this goes through Shl as a result of reduceStrength(), we will currently do this: tmp mapping: @1 -> %tmp1 @2 -> %tmp2 Move %tmp1, %tmp2 Add32 %tmp1, %tmp2 This prevents us from coalescing %tmp1 and %tmp2, since their live ranges overlap. The solution is that when we decide to emit the result move, we also force a temporary substitution of s/%tmp1/%tmp2/g on the subsequent Inst. This would cause us to do: Move %tmp1, %tmp2 Add32 %tmp2, %tmp2 I believe that such a substitution is both correct and optimal. It's correct because we use arguments before we def them, so although the Add32 def's %tmp2, this happens after all arguments are consumed. Hence, %tmp2 is a correct substitute for %tmp1. It's also optimal, since it avoids the overlapping live range. We have to be somewhat careful about how we implement this. Probably, the temporary substitution will be something that only some lowering rules opt into.
LOL, I picked a bad example. We have special-case handling of Shl(x, 1), and Add(x, x) turns into Shl(x, 1). That handling already does the right thing. But this same issue arises for Mul, for example.
Hmm! It looks like the register allocator already does magically good things about the Mul case...
Whoa, our register allocator already does the magically correct thing. This is Ben's comment: // We do not want the Use() of this move to interfere with the Def(), even if it is live // after the Move. If we were to add the interference edge, it would be impossible to // coalesce the Move even if the two Tmp never interfere anywhere. This is the verbiage in the IRC paper: Move instructions are given special consideration. It is important not to create artifical interferences between the source and destination of a move. Consider the program: t := s ... x := ... s ... ... y := ... t ... ; copy ; use of s ; use of t After the copy instruction both s and t are live, and an interference edge would be added between s and t, since t is being defined at a point where s is live. The solution is to temporarily remove s from the live set and continue.