[staleness] improve staleness performance

_From [derek.br...@gmail.com](https://code.google.com/u/117968039472581148324/) on December 10, 2010 19:52:17_

PR 553724

for performance I plan to:

don't watch nonheap:
- nonheap sharing: if last was nonheap and this is related just ignore
- unsafe: ignore esp-based refs
for ebp-based: track whether frame pointer

already have option, need to study:
- measure -no_stale_blind_store

if successful, apply these to Dr. Memory too:
- eliminate and of mask by using index w/ scale
- store displacement instead of abs addr: then can add directly to
orig addr instead of computing lower bits

use Dr. Memory opts wasn't able to in prototype:
- xl8 sharing: need way to exit on over/underflow

two more:
- measure mem usage: storing staleness per snapshot can add a lot
- should -stale_granularity be increased as -dump_freq increases?
for a long-running app it seems fine to make the staleness data
coarser and coarser, which also improves performance.

more optimization ideas. maybe should split this PR up:

--------------------------------------------------
lahf followed by read of eax causes partial register stall:
can we keep in eax longer?

--------------------------------------------------
can switch to per-16-byte shadow, right, since always have 8-byte header?

--------------------------------------------------
eliminate restore prior to lea when last app instr wrote that reg:
+37 L3 64 8b 0d 18 00 00 00 mov %fs:0x18 -> %ecx
+44 L4 64 89 0d d0 0e 00 00 mov %ecx -> %fs:0x00000ed0
+51 L4 64 8b 0d d0 0e 00 00 mov %fs:0x00000ed0 -> %ecx
+58 L4 8d 59 24 lea 0x24(%ecx) -> %ebx
may need to split the used field to indicate where real value is:
in TLS, in reg, both, dead, etc.
xref PR 494720

Another redundancy to remove: restored post-app-write, then re-restored at
end of bb, w/ no change to reg in between. I already tried just having
restore set used=false but it's not working even on hello.exe. I didn't
take the time to figure out why after I fixed the first bug which was an
add_shadow_table_lookup() error in marking scratch regs. Lumping into this
case since a similar optimization.

documenting some of the perf #s from my notes
this was on my laptop so these are Windows spec2k

on laptop, whether using OP_and or not, and whether using shr-16 or movzx,
don't make much difference, all are around (note that these are w/ defaults
-staleness so check-leak instrumentation is present):
Benchmark # Status %CPU Time(min) RSS(KB) VSz(KB)
crafty- 1/1 ok \* 3\* 0.38 0 0
eon- 1/1 ok _13_ 0.33 0 0
gzip- 1/1 ok \* 3\* 0.35 0 0
twolf- 1/1 ok _12_ 0.10 0 0
vortex*\* 1/1 ok -- 1.50 0 0

yet eliminating redundant eflags save+re-restore makes a huge difference
(pretty sure this is the only change causing this: I measured w/o the
ignore-lea, and got these same #s, so lea having no effect):
Benchmark # Status %CPU Time(min) RSS(KB) VSz(KB)
crafty- 1/1 ok \* 6\* 0.24 0 0
eon- 1/1 ok _14_ 0.32 0 0
gzip- 1/1 ok \* 4\* 0.28 0 0
twolf- 1/1 ok _14_ 0.09 0 0
vortex- 1/1 ok \* 1\* 1.27 0 0

using extra spill (or xchg-w/-reg when avail) instead of xchg-w/-mem for
eflags => Qin was right to be concerned about xchg w/ memory:
Benchmark # Status %CPU Time(min) RSS(KB) VSz(KB)
crafty- 1/1 ok \* 5\* 0.22 0 0
eon- 1/1 ok _15_ 0.33 0 0
gzip- 1/1 ok \* 5\* 0.23 0 0
twolf- 1/1 ok _16_ 0.09 0 0
vortex- 1/1 ok \* 1\* 1.16 0 0

using disp saves only 2 bytes here
=> very little effect, .01 min faster on eon+gzip but in the noise:
Benchmark # Status %CPU Time(min) RSS(KB) VSz(KB)
crafty- 1/1 ok \* 7\* 0.22 0 0
eon- 1/1 ok _17_ 0.32 0 0
gzip- 1/1 ok \* 6\* 0.24 0 0
twolf- 1/1 ok _18_ 0.09 0 0
vortex- 1/1 ok \* 1\* 1.16 0 0

eliminate slowpath for just about everything (rep cmps is one notable thing not yet handled: not hard to do though)
=> anything w/ up to 1 src mem and up to 1 dst mem, but ruling out xlat
(which does occur in twolf) b/c its base-disp is unique:
Benchmark # Status %CPU Time(min) RSS(KB) VSz(KB)
crafty- 1/1 ok \* 6\* 0.23 0 0
eon- 1/1 ok _17_ 0.31 0 0
gzip- 1/1 ok _11_ 0.13 0 0
twolf- 1/1 ok _21_ 0.08 0 0
vortex- 1/1 ok \* 1\* 0.77 0 0

I implemented several of the ideas above:
- Eliminate and of mask by using index w/ scale.
This reduces staleness instrumentation size by 18%.
This is in shared code and it also improves Dr. Memory performance
and reduces Dr. Memory instrumentation size.
- Do not monitor esp-based memory references.
Option -no_stale_ignore_sp can be used to disable this optimization.
- Ignore OP_lea
- Do not re-save (and then restore) eflags if there was no earlier save
- Do not use xchg-with-mem for eflags save/restore b/c it locks the bus
- Store displacement instead of absolute address of shadow block.
For staleness w/ a scale, this only saves 2 bytes but better than
nothing.
- Use own slowpath conditions instead of Dr. Memory's: able to eliminate
essentially all slowpath instances by assuming that any one memory
reference, regardless of size (including rep string ops), will only touch
one memory allocation.

I'm leaving the remaining ideas, including applying "store-disp" to
Dr. Memory, for future work.
- Dr. Heapstat now attempts to avoid repeated new peak snapshots by
not recording a new snapshot if it is within a threshold of the current
snapshot in each of three categories:
- total memory usage
- number of allocations and frees (i.e., the constituent allocations making
up the existing peak have not changed much)
- timestamp (i.e., the new peak is not substantially later in the
program's execution).
The threshold used is a percentage and is controlled by a new
-peak_threshold option.
- added docs for this
- I measured -no_stale_blind_store and found it is faster on pretty much
everything except crafty: so crafty was a bad choice of initial metric.

> /work/dr/tot/opensource/tools/bmcmp.pl -k release/glaurung/stale-noebp-noblind-2010-Jun3/tk-release release/glaurung/stale-noebp-2010-Jun2/tk-release
# in dir /work/dr/tot/internal/suite:
## # release/glaurung/stale-noebp-noblind-2010-Jun3/tk-release / release/glaurung/stale-noebp-2010-Jun2/tk-release

```
Benchmark Status Time RSS VSz
bzip2 FAIL/FAIL 0.982 ----- -----
crafty ok/ok 1.072 ----- -----
eon ok/ok 0.970 ----- -----
gap ok/ok 1.005 ----- -----
gcc ok/ok 0.989 ----- -----
gzip FAIL/FAIL 1.015 ----- -----
mcf ok/ok 0.867 ----- -----
parser ok/ok 0.931 ----- -----
twolf ok/ok 0.929 ----- -----
vortex ok/ok 0.939 ----- -----
vpr ok/ok 0.823 ----- -----
```
---

harmonic mean 0.952 ----- -----

=> turning off -stale_blind_store by default. only crafty wants it on
- already did this for staleness: now applying to Dr. Memory
- no changes are needed on the write fault path for special shadow
blocks b/c that's after xl8
- saves 4 bytes in the shadow xl8 path: 2% overall code cache size reduction
- unfortunately, the offs within the shadow block is no longer directly
available, so the esp adjust fastpath has to calculate it explicitly now.

_Original issue: http://code.google.com/p/drmemory/issues/detail?id=222_