Modify bitstream reader to allow parallel parses.

Modify bitstream reader to allow parallel parses.

This is a resubmission of CL https://codereview.chromium.org/1838203002,
after it got reverted.

The previous CL fixed class NaClBitstreamReader to allow parallel
parses. In particular, it made the global abbreviations a shared object,
so that it can be shared by other bitstream readers.

To make the overhead small, the lookup map of global abbreviations was
initialized up front with all known block IDs, rather than incrementally
updating. This reduced the locking considerably in that the block ID
lookup no longer needs a lock.

The reason that the previous CL was reverted was because of the
presumption that all block IDs are known. This meant that the bitstream
reader had to deal with bad block IDs. This breaks the parsing
philosophy that the issue should be returned to the parser so that it
can report the error appropriately, and if possible, error recover as
well.

The fix added to the previous CL is to add a second "unknown" lookup map
that uses a lock to update. This restores the incremental behavior, even
if much slower. Since such unknown cases represent error cases, the slow
behavior should be acceptable.

This code also assumes that parallel parsing is done with 1 driver parse
thread, and n helper parse threads to parse function blocks. The
driver thread is responsible for parsing the memory object, and
spawning off parallel parses for each function block. To guarantee
correctness (since memory objects may be dynamically filled), the
driver parser should build a buffer and copy the corresponding bytes
of the function block into that buffer, before spawning off the
parallel parser to parse it.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4363
R=stichnot@chromium.org, jpp@chromium.org

Committed: https://chromium.googlesource.com/native_client/pnacl-llvm/+/f6a5f463657a536ef3f55ce4b4704a7131e4f7ca

[Karl, 2016-03-30 15:49:04]

Description was changed from

==========
Modify bitstream reader to allow parallel parses.

This is a resubmission of CL https://codereview.chromium.org/1838203002,
after it got reverted.

The previous CL fixed class NaClBitstreamReader to allow parallel
parses. In particular, it made the global abbreviations a shared object,
so that it can be shared by other bitstream readers.

To make the overhead small, the lookup map of global abbreviations was
initialized up front with all known block IDs, rather than incrementally
updating. This reduced the locking considerably in that the block ID
lookup no longer needs a lock.

The reason that the previous CL was reverted was because of the
presumption that all block IDs are known. This meant that the bitstream
reader had to deal with bad block IDs. This breaks the parsing
philosophy that the issue should be returned to the parser so that it
can report the error appropriately, and if possible, error recover as
well.

The fix added to the previous CL is to add a second "unknown" lookup map
that uses a lock to update. This restores the incremental behavior, even
if much slower. Since such unknown cases represent error cases, the slow
behavior should be acceptable.

This code also assumes that parallel parsing is done with 1 driver parse
thread, and n helper parse threads to parse function blocks. The
driver thread is responsible for parsing the memory object, and
spawning off parallel parses for each function block. To guarantee
correctness (since memory objects may be dynamically filled), the
driver parser should build a buffer and copy the corresponding bytes
of the function block into that buffer, before spawning off the
parallel parser to parse it.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4363
R=jpp@chromium.org, stichnot@chromium.org
==========

to

==========
Modify bitstream reader to allow parallel parses.

This is a resubmission of CL https://codereview.chromium.org/1838203002,
after it got reverted.

The previous CL fixed class NaClBitstreamReader to allow parallel
parses. In particular, it made the global abbreviations a shared object,
so that it can be shared by other bitstream readers.

To make the overhead small, the lookup map of global abbreviations was
initialized up front with all known block IDs, rather than incrementally
updating. This reduced the locking considerably in that the block ID
lookup no longer needs a lock.

The reason that the previous CL was reverted was because of the
presumption that all block IDs are known. This meant that the bitstream
reader had to deal with bad block IDs. This breaks the parsing
philosophy that the issue should be returned to the parser so that it
can report the error appropriately, and if possible, error recover as
well.

The fix added to the previous CL is to add a second "unknown" lookup map
that uses a lock to update. This restores the incremental behavior, even
if much slower. Since such unknown cases represent error cases, the slow
behavior should be acceptable.

This code also assumes that parallel parsing is done with 1 driver parse
thread, and n helper parse threads to parse function blocks. The
driver thread is responsible for parsing the memory object, and
spawning off parallel parses for each function block. To guarantee
correctness (since memory objects may be dynamically filled), the
driver parser should build a buffer and copy the corresponding bytes
of the function block into that buffer, before spawning off the
parallel parser to parse it.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4363
R=jpp@chromium.org, stichnot@chromium.org
==========

[Karl, 2016-03-30 15:49:04]

kschimpf@google.com changed reviewers:
+ sehr@chromium.org

[Karl, 2016-03-30 15:54:42]

Don't bother reviewing yet. I discovered a flaw in the implementation!

[Karl, 2016-03-30 16:11:57]

I fixed the bug and the code is ready for review. Please review!

The problem was that I used class BlockInfo as the range of the InfosMap. This
is a problem because the code assumes that these BlockInfo's do not move. To fix
this, I changed the range to be std::unique_ptr<BlockInfo> and dynamically
allocated.

[Jim Stichnoth, 2016-03-30 17:57:03]

lgtm

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
File include/llvm/Bitcode/NaCl/NaClBitstreamReader.h (right):

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
include/llvm/Bitcode/NaCl/NaClBitstreamReader.h:155: static
std::shared_ptr<BlockInfoRecordsMap> create() {
The somewhat unwieldy "std::shared_ptr<BlockInfoRecordsMap>" is used 3 times -
maybe use a typedef?

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
include/llvm/Bitcode/NaCl/NaClBitstreamReader.h:186: UpdateLock &operator=(const
UpdateLock&) = delete;
Delete the default copy ctor?

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
include/llvm/Bitcode/NaCl/NaClBitstreamReader.h:601: return uintptr_t(BitNo/8) &
~(sizeof(word_t)-1);
Can these "8" magic constants be replaced with CHAR_BIT or whatever is
appropriate?

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
include/llvm/Bitcode/NaCl/NaClBitstreamReader.h:626: uintptr_t ByteNo =
getStartWordByteForBit(BitNo);
const?

[Karl, 2016-03-30 19:46:47]

Description was changed from

==========
Modify bitstream reader to allow parallel parses.

This is a resubmission of CL https://codereview.chromium.org/1838203002,
after it got reverted.

The previous CL fixed class NaClBitstreamReader to allow parallel
parses. In particular, it made the global abbreviations a shared object,
so that it can be shared by other bitstream readers.

To make the overhead small, the lookup map of global abbreviations was
initialized up front with all known block IDs, rather than incrementally
updating. This reduced the locking considerably in that the block ID
lookup no longer needs a lock.

The reason that the previous CL was reverted was because of the
presumption that all block IDs are known. This meant that the bitstream
reader had to deal with bad block IDs. This breaks the parsing
philosophy that the issue should be returned to the parser so that it
can report the error appropriately, and if possible, error recover as
well.

The fix added to the previous CL is to add a second "unknown" lookup map
that uses a lock to update. This restores the incremental behavior, even
if much slower. Since such unknown cases represent error cases, the slow
behavior should be acceptable.

This code also assumes that parallel parsing is done with 1 driver parse
thread, and n helper parse threads to parse function blocks. The
driver thread is responsible for parsing the memory object, and
spawning off parallel parses for each function block. To guarantee
correctness (since memory objects may be dynamically filled), the
driver parser should build a buffer and copy the corresponding bytes
of the function block into that buffer, before spawning off the
parallel parser to parse it.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4363
R=jpp@chromium.org, stichnot@chromium.org
==========

to

==========
Modify bitstream reader to allow parallel parses.

This is a resubmission of CL https://codereview.chromium.org/1838203002,
after it got reverted.

The previous CL fixed class NaClBitstreamReader to allow parallel
parses. In particular, it made the global abbreviations a shared object,
so that it can be shared by other bitstream readers.

To make the overhead small, the lookup map of global abbreviations was
initialized up front with all known block IDs, rather than incrementally
updating. This reduced the locking considerably in that the block ID
lookup no longer needs a lock.

The reason that the previous CL was reverted was because of the
presumption that all block IDs are known. This meant that the bitstream
reader had to deal with bad block IDs. This breaks the parsing
philosophy that the issue should be returned to the parser so that it
can report the error appropriately, and if possible, error recover as
well.

The fix added to the previous CL is to add a second "unknown" lookup map
that uses a lock to update. This restores the incremental behavior, even
if much slower. Since such unknown cases represent error cases, the slow
behavior should be acceptable.

This code also assumes that parallel parsing is done with 1 driver parse
thread, and n helper parse threads to parse function blocks. The
driver thread is responsible for parsing the memory object, and
spawning off parallel parses for each function block. To guarantee
correctness (since memory objects may be dynamically filled), the
driver parser should build a buffer and copy the corresponding bytes
of the function block into that buffer, before spawning off the
parallel parser to parse it.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4363
R=stichnot@chromium.org, jpp@chromium.org

Committed:
https://chromium.googlesource.com/native_client/pnacl-llvm/+/f6a5f463657a536e...
==========

[Karl, 2016-03-30 19:46:48]

Committed patchset #3 (id:40001) manually as
f6a5f463657a536ef3f55ce4b4704a7131e4f7ca (presubmit successful).

[Karl, 2016-03-30 19:47:30]

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
File include/llvm/Bitcode/NaCl/NaClBitstreamReader.h (right):

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
include/llvm/Bitcode/NaCl/NaClBitstreamReader.h:155: static
std::shared_ptr<BlockInfoRecordsMap> create() {
On 2016/03/30 17:57:02, stichnot wrote:
> The somewhat unwieldy "std::shared_ptr<BlockInfoRecordsMap>" is used 3 times -
> maybe use a typedef?

Done.

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
include/llvm/Bitcode/NaCl/NaClBitstreamReader.h:186: UpdateLock &operator=(const
UpdateLock&) = delete;
On 2016/03/30 17:57:02, stichnot wrote:
> Delete the default copy ctor?

Done.

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
include/llvm/Bitcode/NaCl/NaClBitstreamReader.h:601: return uintptr_t(BitNo/8) &
~(sizeof(word_t)-1);
On 2016/03/30 17:57:02, stichnot wrote:
> Can these "8" magic constants be replaced with CHAR_BIT or whatever is
> appropriate?

Fixed all occurrences in file.

https://codereview.chromium.org/1843673003/diff/20001/include/llvm/Bitcode/Na...
include/llvm/Bitcode/NaCl/NaClBitstreamReader.h:626: uintptr_t ByteNo =
getStartWordByteForBit(BitNo);
On 2016/03/30 17:57:02, stichnot wrote:
> const?

Done.