[DynInst_API:] Commit: StackAnalysis and StackMod improvements

[Matt Morehouse <mm@xxxxxxxxxxx>]

Hi everyone,

Changes to StackAnalysis include performance improvements, reduced memory usage, more accurate stack height determinations, and bug fixes.  The introduction of limited memory tracking has also increased the number of functions instrumentable by StackMod.

Changes to StackMod include reduced memory usage and bug fixes.

To help quantify the improvements, I've instrumented the SPEC CPU2006 benchmark suite with stack canaries and collected the data below.  Note that instrumentation times are hardware-dependent, but the before/after ratio should be fairly consistent across different hardware.

Also note that a fair chunk of the "instrumentable" functions before the improvements were not actually safe to instrument.  Before improvements, StackAnalysis was assuming in many cases that memory loads do not affect the contents of the target register (i.e. memory loads don't actually load anything).  After fixing this inaccuracy, the percentage of instrumentable functions was closer to 50%.

- Matt Morehouse

Commit summaries, in chronological order, are below:

Commit: d711bbf0b06fd2f036c7cbf045690a08ec3b509b

Fixed bug related to falsely recognizing memory accesses

Some instructions were being incorrectly identified as accessing memory.

--------------------------------------------------------------------------

Commit: 1bf6f63427ac132032091681d66544880277ffef

Fixed segfault on instantiation of non-seeded Randomize objects

--------------------------------------------------------------------------

Commit: 5254d217818a2d97d78763e19751bfc58d5a8c5a

Fixed issue with tail call recognition

We now use the exitBlocks() method instead of callEdges() due to
changes in ParseAPI.

--------------------------------------------------------------------------

Commit: 8c738f2f8960f49c5c4c62a058eaf32e6d2d606e

Made several improvements to our stack analysis code.

1. Added handler for XOR zeroing.
2. Set caller-save registers to topBottom after a function call
    rather than bottom (as before).
3. Set registers containing memory-loaded values to bottom rather
    than topBottom (as before).

---------------------------------------------------------------------------

Commit: dd1818f341e997d6818acd62306f7030845242cb

Implemented basic memory tracking for stack analysis.

Addresses that can be statically determined (e.g. global variables)
are now tracked in the same manner as registers. Currently only the
MOV instruction is handled for memory loads and stores. There are
plans to add sign/zero extends in the near future.

---------------------------------------------------------------------------

Commit: 16d6940bd437f5d78a467657ebfb237ba59519d7

Improved LEA handling and added mul/div handling.

---------------------------------------------------------------------------

Commit: 41d213e1506cd8d8b360232e76c80b1ff331e85d

Tightened up add/sub handling and added support for addsd/movsd.

---------------------------------------------------------------------------

Commit: e9ac0550d3f90c1228c484f433701944782ae300

Implemented naive stack slot tracking.

This is done by performing a second fixpoint analysis after
register stack heights are determined in the first fixpoint
analysis.

---------------------------------------------------------------------------

Commit: 0aac6edff3703664ce946ef2ea8b54a23f626e0e

Memory leak fixes and stopped tracking topped locations.

Various data structures were being dynamically allocated and never
freed.  Some of these structures I was able to switch to stack
allocation and others I was able to free when they were no longer
needed.

Additionally, several std::map objects were maintaining entries for
locations that did not contain stack heights.  By eliminating these
entries, I was able to drastically reduce memory consumption while
speeding up the fixpoint analysis.

----------------------------------------------------------------------------

Commit: 88cb7380c82641c17be1a41b25e39e317b016049

Started topping loads from undetermined (topped) locations.

Also made modifications to StackMod so that storing stack pointers
to topped locations results in the function being uninstrumentable.

-----------------------------------------------------------------------------

Commit: 38e1aaf319ca491d2686ddffdb18cbece5d7bee1

Improved handling of sign/zero extends.

Extended memory-tracking to include sign/zero extends, made sign/
zero extends from topped locations yield topped values, and
implemented better handling of CBW and CWDE instructions.

------------------------------------------------------------------------------

Commit: 564ad955d15c29a92f6d929a819cfff1a63f6095

Stopped bottoming target registers of add/sub in some situations.

When add/sub reads an argument from a topped memory location, we
now round the target register to top or bottom rather than always
setting it to bottom.

------------------------------------------------------------------------------