CSE doens't only identify; it eliminates (hence the E!). It refers to the complete solution. I don't think you necessarily have to compute the dominance relati

CSE doens't only identify; it eliminates (hence the E!). It refers to the complete solution. I don't think you necessarily have to compute the dominance relation because it can pop out implicitly. If CSE is done on intermediate code, the dominance relation will pop out from thedirecton in which the instructions are followed around the basic blocks. E.g. simple case: we see t3 <= t2 + t1. So we make a note in some CSE hash table that we had a t2 + t1, and that the result is cached in t3. Then if we see t2 + t1 again in the same basic block, we can replace that with t3. The dominance relation is that earlier instructions in the basic block dominate later ones, but we don't have to explicitly calculate it.