[jxors]

Evaluating how much of instruction space we cover was indeed difficult. Initially, we wanted to parse Intel XED's datafiles to generate a map of valid instruction space, but we ended up going for the simpler approach of computing coverage by selecting instructions randomly and from real-world binaries because of time constraints.

From Table 7 you can get an idea of how many instruction variants we cover (~1500 covered, ~700 enumerated but not synthesized, 744 out of enumeration scope). Instruction variants correspond much more closely with the mnemonics listed in the reference manuals, and this is typically the number reported by related work.

[saagarjha]

Yes, but I still think this falls victim to the problem I mentioned: you might have two dozen arithmetic instructions, and two that change privilege state. It is generally the latter that is more interesting to those doing this kind of analysis. (Not saying that the former is completely useless; I am sure emulator developers and similar would find it interesting. But most of the research effort going into finding new instructions or whatever is going towards the not-simple instructions.)