Fix translator handling of basic block indices.

Fix translator handling of basic block indices.

The code used to use a vector to hold basic blocks associated with
indices. This had two problem: 1) The "number of blocks" record would
generate a vector of the given size (even if very large); and 2)
Indices would expand the vector to define the index (even if very
large).

In most cases, such large values are incorrect. To fix this, this
patch uses a map from block index, to the corresponding basic block.
Only after all basic block indices have been processed, we check that
the size makes sense, and convert it to a vector.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4261
R=jpp@chromium.org, stichnot@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=ac7d73441e1c599108b20c4702a96db0e956889e

[Karl, 2015-08-06 16:21:47]

kschimpf@google.com changed reviewers:
+ jpp@chromium.org, jvoung@chromium.org, stichnot@chromium.org

[John, 2015-08-06 17:22:54]

lgtm

Just suggestions. LGMT otherwise.

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp#newcode65
src/IceCfg.cpp:65: Nodes = NewNodes;
The CL description mentions "large numbers." So, I assume NewNodes is
potentially very large.

NodeList is not a list, is a std::vector, so copying is not super efficient. The
calls to replaceNodes below don't care about what happens to NewNodes. Why not
turning NewNodes into a non-const pointer, and using swap?

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp#newcode370
src/IceCfg.cpp:370: NodeList Reordered;
Reordered.reserve(Placed.size() + Unreachable.size())?

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp
File src/PNaClTranslator.cpp (right):

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1312: CfgNodeMap BbMap;
The only operations you perform in BbMap are insert and find. Given that you do
not traverse it, what about using a std::unordered_map instead? Alternatively,
you can use the sorted property of std::map and iterate over it in verify and
rename basic blocks instead of performing O(n lg(n)) lookups.

[Jim Stichnoth, 2015-08-06 17:24:33]

I'm finding differences in BB names when translating spec2k, still
investigating...

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (left):

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp#oldcode371
src/IceCfg.cpp:371: assert(Nodes.size() == OldSize);
Can you preserve the size assert?  This is to make sure we haven't lost (or
gained...) any nodes during the reordering.  Here and below.

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp#newcode66
src/IceCfg.cpp:66: for (size_t i = 0, sz = Nodes.size(); i < sz; ++i)
for (SizeT I = 0, NumNodes = getNumNodes(); I < NumNodes; ++I)

(sorry, I don't like the capitalization either)

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.h#newcode93
src/IceCfg.h:93: // Replace nodes of cfg with given list of nodes.
Should this be a "///" comment for doxygen?

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp
File src/PNaClTranslator.cpp (right):

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1290: CfgNodeMap::iterator pos = BbMap.find(Index);
Pos

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1294: BbMap.insert(std::make_pair(Index, Bb));
I kinda prefer the clarity of this:
  BbMap[Index] = Bb;
but your call.

Could also consider this for the whole body:

  assert(!isIRGenerationDisabled());
  if (BbMap[Index] == nullptr)
    BbMap[Index] = Func->makeNode();
  return BbMap[Index];

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1299: typedef std::map<NaClBcIndexSize_t, Ice::CfgNode*>
CfgNodeMap;
unordered_map

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1969: StrBuf << "Function specified " << SpecifiedNumBbs
Add "blocks" or "basic blocks" to the message

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:2903: if (Ice::BuildDefs::dump()) {
Can you put the BuildDefs::dump() check at the very beginning?

[Jim Stichnoth, 2015-08-06 18:17:09]

On 2015/08/06 17:24:33, stichnot wrote:
> I'm finding differences in BB names when translating spec2k, still
> investigating...

Looks like that's WAI.  After phi lowering, new nodes are inserted into the
middle, and renumbering/renaming happens.

[Karl, 2015-08-06 18:55:52]

Sent out for re-review just to verify changes have been met.

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (left):

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp#oldcode371
src/IceCfg.cpp:371: assert(Nodes.size() == OldSize);
On 2015/08/06 17:24:33, stichnot wrote:
> Can you preserve the size assert?  This is to make sure we haven't lost (or
> gained...) any nodes during the reordering.  Here and below.

Added assert back.

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp#newcode65
src/IceCfg.cpp:65: Nodes = NewNodes;
On 2015/08/06 17:22:54, John wrote:
> The CL description mentions "large numbers." So, I assume NewNodes is
> potentially very large.
> 
> NodeList is not a list, is a std::vector, so copying is not super efficient.
The
> calls to replaceNodes below don't care about what happens to NewNodes. Why not
> turning NewNodes into a non-const pointer, and using swap?

Done.

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp#newcode66
src/IceCfg.cpp:66: for (size_t i = 0, sz = Nodes.size(); i < sz; ++i)
On 2015/08/06 17:24:33, stichnot wrote:
> for (SizeT I = 0, NumNodes = getNumNodes(); I < NumNodes; ++I)
> 
> (sorry, I don't like the capitalization either)

Done.

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.cpp#newcode370
src/IceCfg.cpp:370: NodeList Reordered;
On 2015/08/06 17:22:54, John wrote:
> Reordered.reserve(Placed.size() + Unreachable.size())?

Done.

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/1275953002/diff/1/src/IceCfg.h#newcode93
src/IceCfg.h:93: // Replace nodes of cfg with given list of nodes.
On 2015/08/06 17:24:33, stichnot wrote:
> Should this be a "///" comment for doxygen?

Done. Also renamed to swapNodes to better match functionality.

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp
File src/PNaClTranslator.cpp (right):

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1290: CfgNodeMap::iterator pos = BbMap.find(Index);
On 2015/08/06 17:24:33, stichnot wrote:
> Pos

Removed. Replaced with simpler code.

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1294: BbMap.insert(std::make_pair(Index, Bb));
On 2015/08/06 17:24:33, stichnot wrote:
> I kinda prefer the clarity of this:
>   BbMap[Index] = Bb;
> but your call.
> 
> Could also consider this for the whole body:
> 
>   assert(!isIRGenerationDisabled());
>   if (BbMap[Index] == nullptr)
>     BbMap[Index] = Func->makeNode();
>   return BbMap[Index];

Did slight modification to your suggestion.

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1299: typedef std::map<NaClBcIndexSize_t, Ice::CfgNode*>
CfgNodeMap;
On 2015/08/06 17:24:33, stichnot wrote:
> unordered_map

Done.

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1312: CfgNodeMap BbMap;
On 2015/08/06 17:22:54, John wrote:
> The only operations you perform in BbMap are insert and find. Given that you
do
> not traverse it, what about using a std::unordered_map instead? Alternatively,
> you can use the sorted property of std::map and iterate over it in verify and
> rename basic blocks instead of performing O(n lg(n)) lookups.

Changed to unordered map.

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:1969: StrBuf << "Function specified " << SpecifiedNumBbs
On 2015/08/06 17:24:33, stichnot wrote:
> Add "blocks" or "basic blocks" to the message

Done.

https://codereview.chromium.org/1275953002/diff/1/src/PNaClTranslator.cpp#new...
src/PNaClTranslator.cpp:2903: if (Ice::BuildDefs::dump()) {
On 2015/08/06 17:24:33, stichnot wrote:
> Can you put the BuildDefs::dump() check at the very beginning?

Done.

[Jim Stichnoth, 2015-08-06 19:41:21]

Otherwise lgtm

https://codereview.chromium.org/1275953002/diff/20001/src/PNaClTranslator.cpp
File src/PNaClTranslator.cpp (right):

https://codereview.chromium.org/1275953002/diff/20001/src/PNaClTranslator.cpp...
src/PNaClTranslator.cpp:39: #include <unordered_map>
Could you move this include into IceDefs.h, and remove it from the other two
places that #include it?

https://codereview.chromium.org/1275953002/diff/20001/src/PNaClTranslator.cpp...
src/PNaClTranslator.cpp:2899: if (isIRGenerationDisabled() ||
!Ice::BuildDefs::dump())
Test for BuildDefs::dump() very first, even before isIRGenerationDisabled(), so
that the function is *completely* empty if dump is not defined.  E.g., swap the
|| operand order.

[Karl, 2015-08-06 19:55:29]

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

[Karl, 2015-08-06 19:55:41]

https://codereview.chromium.org/1275953002/diff/20001/src/PNaClTranslator.cpp
File src/PNaClTranslator.cpp (right):

https://codereview.chromium.org/1275953002/diff/20001/src/PNaClTranslator.cpp...
src/PNaClTranslator.cpp:39: #include <unordered_map>
On 2015/08/06 19:41:21, stichnot wrote:
> Could you move this include into IceDefs.h, and remove it from the other two
> places that #include it?

Done.

https://codereview.chromium.org/1275953002/diff/20001/src/PNaClTranslator.cpp...
src/PNaClTranslator.cpp:2899: if (isIRGenerationDisabled() ||
!Ice::BuildDefs::dump())
On 2015/08/06 19:41:21, stichnot wrote:
> Test for BuildDefs::dump() very first, even before isIRGenerationDisabled(),
so
> that the function is *completely* empty if dump is not defined.  E.g., swap
the
> || operand order.

Done.