Hi all,

I have been working on Asan global optimization pass lately. The goal is 
to remove redundant Asan checks from sanitized code. This should 
hopefully reduce Asan's speed/size overhead (which is currently ~2x). 
The patch is not yet ready for trunk (e.g. I haven't done bootstrap, 
etc. but Asan testsuite passed wo errors) but I thought I'd send it for 
preliminary review of algorithm and data structures (*).

Current implementation (based on existing sanopt pass) uses a simple 
iterative intra-procedural dataflow to compute information about living 
checks. For each pointer we track the size of memory that was already 
checked for it. During dataflow iterations, living checks are merged at 
blocks start in a natural way.

I decided to keep current (local) Asan optimizations because they reduce 
compilation time by dropping many obviously redundant checks much 
earlier in the compilation pipeline.

Current results seem to be encouraging: the pass was able to remove 112 
checks (out of 1768) in gcc/asan.c without significant increase in 
sanopt pass runtime.

Before upstreaming this code, I plan to
1) develop extensive set of tests to make sure that sanopt performs 
conservative optimization i.e. does not remove checks too agressively (I 
guess this is a critically important prerequisite so any suggestions are 
welcomed)
2) disable optimizations for very large functions to avoid unbearable 
compile times
3) do detailed performance and efficiency measuments for Asan-bootstrap

I also have some ideas for improving this code (and I'm certainly open 
to suggestions from community):
1) propagating checking information through assignments and PHI-nodes 
(and maybe even pointer arithmetic) should improve efficiency
2) ditto for optimization of symbolic ranges; actually this looks like a 
relatively easy addition to current code (I just need to keep a list of 
checked symbolic ranges to check_info structure)
3) in addition to redundant check removal, we could also move duplicate 
checks from e.g. branches of if-statement to their dominators.

-Y

(*) The patch relies on some additional changes in hash-table and CFG 
which have not yet been upstreamed so it won't go with current trunk.