BTW I looked around a bit and found another similar system, based on QEMU instead of Valgrind, claiming to be faster, ie less runtime overhead while tracing, and also supporting kernel mode:
http://wiki.nss.cs.ubc.ca/Tralfamadore
Edit: never mind, the program does not seem to be publicly available, just papers
Wow, I was looking for something exactly like this a while ago, but was unable to find it. I notice that these days with Google it's really hard to find a tool or project when you're looking for it especially if it's more obscure. Might be a consequence of the ranking rules that crowd lesser known pages out.