Do you have experience with valgrind? Can you compare & contrast the two?
Also, I thought that the compiler additions was implemented years ago, several times (tristan gingold's "checker-gcc" first, then the bounds-checking patches and most recently "-fmudflap"), so that asan's functionality would basically only require rewriting libmudflap - but it apparently requires a much deeper surgery of gcc. Can anyone familiar with asan and/or the previous implementations comment on that?
I've used most of the tools on that page, including Valgrind. Valgrind interprets your program, and hooks loads, stores, malloc/free, etc. to track memory usage. ASan is a compiler pass that inserts extra instructions around loads and stores to drive per-address state machines that live in a shadow area of memory.
Valgrind is slow (20x-50x for serial programs, more for parallel programs because Valgrind only executes one thread at a time), but can detect reads from uninitialized memory because your program is essentially executing in a VM. ASan is much faster, especially if the compiler pass can avoid instrumenting some loads/stores based on static analysis, and cannot detect reads from uninitialized memory, but can detect most other kinds of memory areas.
They're both thread-safe, so you can use them to debug parallel programs. As mentioned above, Valgrind is much slower at this, and until recently  you would never see most race conditions in multithreaded programs because Valgrind's schedule would run each thread until it yielded voluntarily, rather than pre-empting and time-multiplexing between threads. In contrast, with ASan all threads are running close to at-speed and simultaneously, so in my case performance was >100x better and I actually saw the race conditions I cared about.
Valgrind supports more platforms than ASan (see  vs. ), and does not require compiler support (so you can use it to debug code from any compiler), but does tend to lag behind new platform features a bit. For example, until recently it borked if you used the new x86_64 RDTSCP instruction.
Mudflap seems similar in concept, but there appear to be issues with the implementation (see "Known Shortcomings" at )
You're probably using ASAN a lot more than sporadically within Google. A lot of the continuous builds run with it on.
I think that's really the biggest advantage ASAN has - it's cheap enough that you can just make it the default when running tests or developing on your local machine, and catch a number of memory errors immediately instead of having to actively debug them.