Add -reorder-basic-blocks option and fix nop insertion

Add -reorder-basic-blocks option and fix nop insertion

1. Basic block reordering can be enabled with -reorder-basic-blocks option enabled.

Blocks will be sorted according to the Reversed Post Traversal Order, but the next
node to visit among all candidate children nodes is selected 'randomly'.

Example:
  A
 / \
B   C
 \ /
  D

This CFG can generate two possible layouts:
A-B-C-D or A-C-B-D

2. Fix nop insetion

Add checks to avoiding insertions in empty basic blocks(dead blocks) and bundle locked instructions.

BUG=
R=jpp@chromium.org, jvoung@chromium.org, stichnot@chromium.org

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

[qining, 2015-07-28 21:53:58]

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

[John, 2015-07-29 17:52:36]

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode340
src/IceCfg.cpp:340: void getRandomReversedPostOrder(NodeType *Node,
Does this need to be a template? It seems NodeType is always CfgNode.

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode344
src/IceCfg.cpp:344: if (Visited.find(Node) != Visited.end())
Just a thought...

You are calling this method, and then checking if the node is not in Visited.
you're also comparing iterators, and always building the end iterator. How about
doing something like

void getRandomReversedPostOrder(...) {
  assert(Visited.count(Node) == 0);
  Visited.insert(Node);
  for (CfgNode *Next = ...) {
    if (Visited.count(Node) == 0) {
      getRandomReversedPostOrder(Next...);
    }
  }
  ReversePostOrder.push_front(Node);
}

when trying to figure out whether a value is in a container, it is usually
better to use .count() == 0 rather than .end()

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode349
src/IceCfg.cpp:349: [&](int N) { return RNG->next(N); });
please do not use default capture (especially by ref). In this case, just use

[RNG](int N)

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode350
src/IceCfg.cpp:350: for (auto *Next : Outs) {
Just a personal preference, but use

CfgNode *

instead of

auto *

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode371
src/IceCfg.cpp:371: for (CfgNode *Node : NewList)
This is probably not a big deal, but you're traversing NewList twice (here and
in the dtor.) How about doing something like

while (!NewList.empty()) {
  Nodes.emplace_back(NewList.front());
  NewList.pop_front();
}

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.h#newcode176
src/IceCfg.h:176: void shuffleNodes();
What is the difference between shuffleNodes and reorderNodes? It seems to me
(just from their names) that they do related/similar/the same thing.

[jvoung (off chromium), 2015-07-29 18:09:18]

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:503: Target->doNopInsertion();
On BundleUnlock what happens? Does it insert nops before the BundleUnlock?

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/nop-insertion.ll (left):

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/nop-insertion.ll:4: 
Why remove REQUIRES: allow_dump ?

Does make -f Makefile.standalone check-lit MINIMAL=1 still work?

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/nop-insertion.ll (right):

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/nop-insertion.ll:14: 
Maybe add a case with --sandbox?

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/reorder-basic-blocks.ll (right):

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/reorder-basic-blocks.ll:2: ; generate different basic
block layout.
Does this REQUIRES: allow_dump also?

[qining, 2015-07-29 23:04:40]

Updated to Patch set 3.

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode340
src/IceCfg.cpp:340: void getRandomReversedPostOrder(NodeType *Node,
On 2015/07/29 17:52:36, John wrote:
> Does this need to be a template? It seems NodeType is always CfgNode.

Done, change to a normal function.

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode344
src/IceCfg.cpp:344: if (Visited.find(Node) != Visited.end())
On 2015/07/29 17:52:36, John wrote:
> Just a thought...
> 
> You are calling this method, and then checking if the node is not in Visited.
> you're also comparing iterators, and always building the end iterator. How
about
> doing something like
> 
> void getRandomReversedPostOrder(...) {
>   assert(Visited.count(Node) == 0);
>   Visited.insert(Node);
>   for (CfgNode *Next = ...) {
>     if (Visited.count(Node) == 0) {
>       getRandomReversedPostOrder(Next...);
>     }
>   }
>   ReversePostOrder.push_front(Node);
> }
> 
> when trying to figure out whether a value is in a container, it is usually
> better to use .count() == 0 rather than .end()

I think your code is faster, I've changed to this, expect this can reduce the
translation overhead.

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode349
src/IceCfg.cpp:349: [&](int N) { return RNG->next(N); });
On 2015/07/29 17:52:36, John wrote:
> please do not use default capture (especially by ref). In this case, just use
> 
> [RNG](int N)

Done.

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode350
src/IceCfg.cpp:350: for (auto *Next : Outs) {
On 2015/07/29 17:52:36, John wrote:
> Just a personal preference, but use
> 
> CfgNode *
> 
> instead of
> 
> auto *

Done.

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.cpp#newcode371
src/IceCfg.cpp:371: for (CfgNode *Node : NewList)
On 2015/07/29 17:52:36, John wrote:
> This is probably not a big deal, but you're traversing NewList twice (here and
> in the dtor.) How about doing something like
> 
> while (!NewList.empty()) {
>   Nodes.emplace_back(NewList.front());
>   NewList.pop_front();
> }

Done.

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfg.h#newcode176
src/IceCfg.h:176: void shuffleNodes();
On 2015/07/29 17:52:36, John wrote:
> What is the difference between shuffleNodes and reorderNodes? It seems to me
> (just from their names) that they do related/similar/the same thing.

They are doing different, but a little bit related things, IMO.

reorderNodes() (based on my understanding) is to 'adjust' the layout after
advancedPhiLowering. Advanced Phi Lowering will create new split basic blocks
and append them at the end of the basic block vector, this reorderNodes() moves
these split blocks to more appropriate places, like behind a predecessor or
before a successor.

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1255303004/diff/20001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:503: Target->doNopInsertion();
On 2015/07/29 18:09:18, jvoung wrote:
> On BundleUnlock what happens? Does it insert nops before the BundleUnlock?

On BundleUnlock, we resume nop insertion. At that time, Next should be pointing
to the next instruction just after bundle_unlock, and Cur should be
bundle_unlock instruction. So nop instructions will be inserted between
bundle_unlock and the next instruction after bundle_unlock, hence there should
not be any nop inserted before BundleUnlock.

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/nop-insertion.ll (left):

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/nop-insertion.ll:4: 
On 2015/07/29 18:09:18, jvoung wrote:
> Why remove REQUIRES: allow_dump ?
> 
> Does make -f Makefile.standalone check-lit MINIMAL=1 still work?

Done. Sorry, I mistakenly removed it, it has been added back.

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/nop-insertion.ll (right):

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/nop-insertion.ll:14: 
On 2015/07/29 18:09:18, jvoung wrote:
> Maybe add a case with --sandbox?

Done.

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/reorder-basic-blocks.ll (right):

https://codereview.chromium.org/1255303004/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/reorder-basic-blocks.ll:2: ; generate different basic
block layout.
On 2015/07/29 18:09:18, jvoung wrote:
> Does this REQUIRES: allow_dump also?

Yes, it requires. Added.

[Jim Stichnoth, 2015-07-30 16:30:51]

https://codereview.chromium.org/1255303004/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1255303004/diff/40001/src/IceCfg.cpp#newcode354
src/IceCfg.cpp:354: }
add "// end of anonymous namespace" comment

https://codereview.chromium.org/1255303004/diff/40001/src/IceCfg.cpp#newcode357
src/IceCfg.cpp:357: std::list<CfgNode *> NewList;
Can you use CfgNodeList instead of list<CfgNode*>?

This will have better memory performance, especially since memory is allocated
locally from the Cfg-local pool.

https://codereview.chromium.org/1255303004/diff/40001/src/IceCfg.cpp#newcode358
src/IceCfg.cpp:358: std::unordered_set<const CfgNode *> Visited;
Can you just make Visited an llvm::BitVector, indexed by CfgNode::getIndex() ?

https://codereview.chromium.org/1255303004/diff/40001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1255303004/diff/40001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:409: // Shuffle basic block order if
-reorder-basic-blocks is enabled.
Call Func->shuffleNodes() unconditionally, and check the flag and do the dump
inside that method.

[qining, 2015-07-30 20:25:55]

Updated to Patch set 4. 

Change the Node container used for DFS from List<> to NodeList(vector), visited
label container from  set<> to llvm::BitVector.

https://codereview.chromium.org/1255303004/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1255303004/diff/40001/src/IceCfg.cpp#newcode354
src/IceCfg.cpp:354: }
On 2015/07/30 16:30:50, stichnot wrote:
> add "// end of anonymous namespace" comment

Done.

https://codereview.chromium.org/1255303004/diff/40001/src/IceCfg.cpp#newcode357
src/IceCfg.cpp:357: std::list<CfgNode *> NewList;
On 2015/07/30 16:30:50, stichnot wrote:
> Can you use CfgNodeList instead of list<CfgNode*>?
> 
> This will have better memory performance, especially since memory is allocated
> locally from the Cfg-local pool.

Done.

https://codereview.chromium.org/1255303004/diff/40001/src/IceCfg.cpp#newcode358
src/IceCfg.cpp:358: std::unordered_set<const CfgNode *> Visited;
On 2015/07/30 16:30:51, stichnot wrote:
> Can you just make Visited an llvm::BitVector, indexed by CfgNode::getIndex() ?

Done. Change Visited to ToVisit. True bits mean nodes not yet be visited.

https://codereview.chromium.org/1255303004/diff/40001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1255303004/diff/40001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:409: // Shuffle basic block order if
-reorder-basic-blocks is enabled.
On 2015/07/30 16:30:51, stichnot wrote:
> Call Func->shuffleNodes() unconditionally, and check the flag and do the dump
> inside that method.

Done. Done the same with nop insertion.

[Jim Stichnoth, 2015-07-30 21:14:33]

https://codereview.chromium.org/1255303004/diff/80001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1255303004/diff/80001/src/IceCfg.cpp#newcode403
src/IceCfg.cpp:403: Unreachable.push_back(Nodes[i]);
Unfortunately, I think I may have led you a bit astray with llvm::BitVector.  We
are depending on Nodes[i]->getIndex()==i but that is no longer necessarily the
case after reorderNodes() runs.

You probably have to change this loop to something like:

  for (CfgNode *Node : Nodes)
    if (ToVisit[Node->getIndex()])
      Unreachable.push_back(Node);

And with that change, you have the option of changing ToVisit[] back to
Visited[] if you like.

https://codereview.chromium.org/1255303004/diff/80001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/reorder-basic-blocks.ll (right):

https://codereview.chromium.org/1255303004/diff/80001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/reorder-basic-blocks.ll:42: 
Remove this trailing blank line, to avoid git warnings.

[qining, 2015-07-30 21:38:32]

Updated to Patch Set 6.

https://codereview.chromium.org/1255303004/diff/80001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1255303004/diff/80001/src/IceCfg.cpp#newcode403
src/IceCfg.cpp:403: Unreachable.push_back(Nodes[i]);
On 2015/07/30 21:14:33, stichnot wrote:
> Unfortunately, I think I may have led you a bit astray with llvm::BitVector. 
We
> are depending on Nodes[i]->getIndex()==i but that is no longer necessarily the
> case after reorderNodes() runs.
> 
> You probably have to change this loop to something like:
> 
>   for (CfgNode *Node : Nodes)
>     if (ToVisit[Node->getIndex()])
>       Unreachable.push_back(Node);
> 
> And with that change, you have the option of changing ToVisit[] back to
> Visited[] if you like.

Done. I think ToVisit is fine, but I don't know whether there are any difference
between setting default to true and setting default to false.

https://codereview.chromium.org/1255303004/diff/80001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/reorder-basic-blocks.ll (right):

https://codereview.chromium.org/1255303004/diff/80001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/reorder-basic-blocks.ll:42: 
On 2015/07/30 21:14:33, stichnot wrote:
> Remove this trailing blank line, to avoid git warnings.

Done.

[Jim Stichnoth, 2015-07-30 21:59:15]

lgtm

https://codereview.chromium.org/1255303004/diff/100001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1255303004/diff/100001/src/IceCfg.cpp#newcode409
src/IceCfg.cpp:409: for (int i = ReversedReachable.size() - 1; i >= 0; i--) {
I forgot to mention this before, but this is probably cleaner:

  for (CfgNode *Node : reverse_range(ReversedReachable))
    Nodes.emplace_back(Node);

It also avoids mixing signed and unsigned types.

[qining, 2015-07-30 22:19:51]

Apply reverse_range in patch set 7

https://codereview.chromium.org/1255303004/diff/100001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1255303004/diff/100001/src/IceCfg.cpp#newcode409
src/IceCfg.cpp:409: for (int i = ReversedReachable.size() - 1; i >= 0; i--) {
On 2015/07/30 21:59:15, stichnot wrote:
> I forgot to mention this before, but this is probably cleaner:
> 
>   for (CfgNode *Node : reverse_range(ReversedReachable))
>     Nodes.emplace_back(Node);
> 
> It also avoids mixing signed and unsigned types.

Done. This looks much better.

[jvoung (off chromium), 2015-07-31 15:30:08]

LGTM too btw

[John, 2015-07-31 16:13:56]

lgtm

[qining, 2015-07-31 16:58:39]

Committed patchset #8 (id:140001) manually as
969f6a33c32f9e7197672fbc911918589f5218bd (presubmit successful).