Prevent unbounded memory consuption of long lived JIT processes

This series of patches address several issues causing memory usage to grow
indefinetely on a long lived process.

These are not convenional leaks -- memory would have been freed when the LLVM
context or/and JIT engine is destroyed -- but for as long as they aren't the
memory is usage effectively ubounded.

The issues were found using valgrind with '--show-reachable=yes' option:
1. Compile a bunch of functions with JIT once; delete the result; and exit
   without destroying LLVM context nor JIT engine. (valgrind will report a
   bunch of unfreed LLVM objects)
2. Do as 1, but compile and delete the functions twice
3. Ditto three times.
4. Etc.

Flawless code should not cause the memory usage to increase when compiling the
same -- ie valgrind's log for every run should show the very same unfreed
objects, regardless of the number of times a given code was compilation, but
that was not the case. The attached patches cover most of the causes for new
objects being allocated.

It should be possible to automate such test, but I didn't get that far.

When the hash function uses object pointers all free entries eventually
become tombstones as they are used at least once, regardless of the size.

DenseMap cannot function with zero empty keys, so it double size to get
get ridof the tombstones.

However DenseMap never shrinks automatically unless it is cleared, so
the net result is that certain tables grow infinitely.

The solution is to make a fresh copy of the table without tombstones
instead of doubling size, by simply calling grow with the current size.

Rehash but don't grow when full of tombstones.

Rehash but don't grow when full of tombstones.

StringMap was not properly updating NumTombstones after a clear or rehash.

This was not fatal until now because the table was growing faster than
NumTombstones could, but with the previous change of preventing infinite
growth of the table the invariant (NumItems + NumTombstones <= NumBuckets)
stopped being observed, causing infinite loops in certain situations.

Prevent infinite growth of the list.

git-send-mail was supposed to send a summary for the patch series, but
it didn't made it somehow. Here it is:

This series of patches address several issues causing memory usage to
grow
indefinitely on a long lived process.

These are not conventional leaks -- memory will be freed when the LLVM
context
or/and JIT engine is destroyed -- but for as long as they aren't the
memory is
usage effectively unbounded.

The issues were found using valgrind with '--show-reachable=yes'
option:
1. Compile a bunch of functions with JIT once; delete the result; and
exit
   without destroying LLVM context nor JIT engine. (valgrind will report
a
   bunch of unfreed LLVM objects)
2. Do as 1, but compile and delete the functions twice
3. Ditto three times.
4. Etc.

Flawless code should not cause the memory usage to increase when
compiling the
same -- ie valgrind's log for every run should show the very same
unfreed
objects, regardless of the number of times a given code was compilation,
but
that was not the case. The attached patches cover most of the causes for
new
objects being allocated.

It should be possible to automate such test, but I didn't get that far.

Jose

Good morning Jose,

Thank you to send patches.

  - Please send patches to llvm-commits.
  - Please make patches with "--attach". You may add "format.attach"
to git config.

I have not seen yours yet, but I pushed yours to github;
https://github.com/chapuni/LLVM/compare/ed4edf9e...jfonseca%2F20110316
(Excuse me I could not input accent)

...Takumi

Thanks for working on this.

Did you measure the performance impact of these changes?

/jakob

I tracked performance with this change with X86 JIT and there was no
measurable difference, but the performance was governed more by the
quality of the compiled code, and not so much the compilation time.

If you can point me to a good compilation time benchmark I can get some
figures.

I'd expect either no measurable impact in compilation time, or a slight
improvement due to smaller memory footprint:

- for patches 1-3 (prevent infinite growth of several hash maps data
types) should above all reduce memory usage; there might be some cases
(e.g., frequent updates with a small bounded number of elements) where
it may trade off an exponentially growing table size (i.e., memory) for
more rehashes (i.e., cpu), but that should be a win on nowadays
processors.

- patch 4 (Reset StringMap's NumTombstones on clears and rehashes)
should improve performance

- patch 5 refers to a function that doesn't get called frequently

Jose

Good morning Jose,

Thank you to send patches.

  - Please send patches to llvm-commits.
  - Please make patches with "--attach". You may add "format.attach"
to git config.

Will do, thanks.

I have not seen yours yet, but I pushed yours to github;
https://github.com/chapuni/LLVM/compare/ed4edf9e...jfonseca%2F20110316
(Excuse me I could not input accent)

...Takumi

Nice. I haven't used github yet, but I'll try using it going forward.

Jose

I normally use 403.gcc, but if you don't have SPEC sources, these tests in the nightly test suite take a while to compile:

MultiSource/Applications/ClamAV
MultiSource/Applications/JM/ldecod
MultiSource/Applications/JM/lencod
MultiSource/Applications/SPASS
MultiSource/Applications/kimwitu++/kc
MultiSource/Applications/sqlite3/sqlite3

If you run 'make TEST=nightly', both llc and opt compile times are interesting. The runtime of opt is cryptically reported in the GCCAS column.

/jakob

Jakob,

Thanks for the detailed instructions.

I've finally got around to build and run the nightly tests, with and without my changes, and times on the GCCAS column vary a few percent on both directions. That is, whatever effect my change has is lost in noise.

I'm going to re-submit my patches to llvm-commits.

Jose

I normally use 403.gcc, but if you don’t have SPEC sources, these tests in the nightly test suite take a while to compile:

MultiSource/Applications/ClamAV

MultiSource/Applications/JM/ldecod

MultiSource/Applications/JM/lencod

MultiSource/Applications/SPASS

MultiSource/Applications/kimwitu++/kc

MultiSource/Applications/sqlite3/sqlite3

If you run ‘make TEST=nightly’, both llc and opt compile times are interesting. The runtime of opt is cryptically reported in the GCCAS column.

I’ve finally got around to build and run the nightly tests, with and without my changes, and times on the GCCAS column vary a few percent on both directions. That is, whatever effect my change has is lost in noise.

Sounds good. Thanks for doing this.

I’m going to re-submit my patches to llvm-commits.

Please do.

/jakob

Done some time ago, but I don’t think they got submitted yet. Is it better to fill in a bug report?

Jose

No, I'll commit it.

/jakob