Short Circuit Evaluation

Short Circuit Evaluation

Split Nodes whenever an early jump is possible by short circuiting boolean
operations. Nodes are split after conservatively checking for side effects,
which include definition of multi block variables, function calls and
instructions involving memory.

BUG=None
R=stichnot@chromium.org

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

[manasijm, 2016-06-15 23:04:26]

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

[John, 2016-06-16 13:41:11]

please add tests to your CL. lit tests are dumb tests, but they are really good
at saving you when something (seemingly) unrelated goes awry...

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

https://codereview.chromium.org/2069923004/diff/1/src/IceCfg.cpp#newcode662
src/IceCfg.cpp:662: auto Node = Nodes.back();
auto*

https://codereview.chromium.org/2069923004/diff/1/src/IceCfg.cpp#newcode666
src/IceCfg.cpp:666: Nodes.push_back(NewNode);
(I think) You are missing short circuiting opportunities here: the algorithm
only short circuits a single operand per block, not the whole control
expression. How about adding a Nodes.push_back(Node) here, and let the algorithm
work on Node again?

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1490
src/IceCfgNode.cpp:1490: void CfgNode::removeInEdge(CfgNode *In) {
add empty line before function definition?

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1493
src/IceCfgNode.cpp:1493: CfgNode *CfgNode::shortCircuit() {
add empty line before function definition?

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1496
src/IceCfgNode.cpp:1496: Variable *Goal = nullptr;
How about renaming this variable (Goal) to Condition...

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1512
src/IceCfgNode.cpp:1512: CfgUnorderedSet<Variable *> Operands;
Instead of creating the unordered set, save a pointer to the instruction.
Remember, these Cfg* data structures allocate data in the CFG local allocator,
and that data will live on until subzero's done lowering the CFG.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1538
src/IceCfgNode.cpp:1538: if ((FoundAnd || FoundOr) && Operands.size() > 1) {
This seems to be optimizing the

a = or i32 x, x

and

a = and i32 x, x

You can still do something sensible here. Just delete the instruction and add a
mov a = x.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1548
src/IceCfgNode.cpp:1548: if (FirstOperandDef == nullptr) {
this should never happens, by contruction, right? If so, add an

assert(false);

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1553
src/IceCfgNode.cpp:1553: // instead of isSingleBlock might introduce more
opportunities.
actually, there are good reasons for this.

1) you need some sort of liveness analysis for last use -- which might not be
available when this is running.

2) it's better to avoid adding multi-block variables to avoid increasing the
site of the liveness bit vectors.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1564
src/IceCfgNode.cpp:1564: auto Dest = It->getDest();
auto*

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1570
src/IceCfgNode.cpp:1570: hasSideEffects = true;
just return nullptr here?

[Jim Stichnoth, 2016-06-20 18:41:41]

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

https://codereview.chromium.org/2069923004/diff/1/src/IceCfg.cpp#newcode660
src/IceCfg.cpp:660: auto Nodes = this->getNodes();
Cfg::getNodes() returns "const NodeList &".  So I'm guessing this use of "auto"
is returning a copy of the node list rather than a reference to the master list.
 Is that what you intended?

Also, I already commented privately, but I'll repeat it here for the record. 
When I tested this patch, I saw that new nodes are being added to the end of
node list, and not necessarily added at the proper topological position.  This
makes the result code more branchy, and also slows down convergence of liveness
analysis.  (Also, it might make live range representation more fragmented which
can slow down register allocation.)

[manasijm, 2016-06-20 20:45:36]

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1490
src/IceCfgNode.cpp:1490: void CfgNode::removeInEdge(CfgNode *In) {
On 2016/06/16 13:41:10, John wrote:
> add empty line before function definition?

Done.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1493
src/IceCfgNode.cpp:1493: CfgNode *CfgNode::shortCircuit() {
On 2016/06/16 13:41:11, John wrote:
> add empty line before function definition?

Done.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1496
src/IceCfgNode.cpp:1496: Variable *Goal = nullptr;
On 2016/06/16 13:41:10, John wrote:
> How about renaming this variable (Goal) to Condition...

Done.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1512
src/IceCfgNode.cpp:1512: CfgUnorderedSet<Variable *> Operands;
On 2016/06/16 13:41:10, John wrote:
> Instead of creating the unordered set, save a pointer to the instruction.
> Remember, these Cfg* data structures allocate data in the CFG local allocator,
> and that data will live on until subzero's done lowering the CFG.

Done.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1548
src/IceCfgNode.cpp:1548: if (FirstOperandDef == nullptr) {
On 2016/06/16 13:41:11, John wrote:
> this should never happens, by contruction, right? If so, add an
> 
> assert(false);
> 

It could happen for valid code, if the condition of the br instruction was
defined in another basic block.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1553
src/IceCfgNode.cpp:1553: // instead of isSingleBlock might introduce more
opportunities.
On 2016/06/16 13:41:11, John wrote:
> actually, there are good reasons for this.
> 
> 1) you need some sort of liveness analysis for last use -- which might not be
> available when this is running.
> 
> 2) it's better to avoid adding multi-block variables to avoid increasing the
> site of the liveness bit vectors.

Acknowledged.

https://codereview.chromium.org/2069923004/diff/1/src/IceCfgNode.cpp#newcode1570
src/IceCfgNode.cpp:1570: hasSideEffects = true;
On 2016/06/16 13:41:11, John wrote:
> just return nullptr here?

Done.

[Jim Stichnoth, 2016-06-27 19:44:41]

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

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfg.cpp#newcode680
src/IceCfg.cpp:680: CfgVector<CfgNode *> Stack{Node};
Can you use NodeList instead of CfgVector<CfgNode *> ?

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfg.cpp#newcode681
src/IceCfg.cpp:681: while(!Stack.empty()) {
Please run "make format"...

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfg.cpp#newcode691
src/IceCfg.cpp:691: for (SizeT i = 0; i < NewList.size(); ++i) {
I think it would be better to use a range-based for loop.

SizeT NodeIndex = 0;
for (auto *Node : NewList) {
  Node->resetIndex(NodeIndex++);
}

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfg.cpp#newcode696
src/IceCfg.cpp:696: 
just one blank line here

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:61: InstPhi &Phi = llvm::cast<InstPhi>(Inst);
auto &

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1579: It++; // Have to split after the def
++It
may be more efficient

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1585: NewNode->setName(getName().append("_2"));
Wrap all the name management inside:
  if (BuildDefs::dump()) { ... }

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1600: auto *Phi = llvm::dyn_cast<InstPhi>(&Inst);
llvm::cast<>

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1622: appendInst(NewInst);
Naively, it looks like there could be a path where NewInst==nullptr, which would
be bad.

I would add "assert(NewInst != nullptr);" here.

https://codereview.chromium.org/2069923004/diff/40001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/short-circuit.ll (right):

https://codereview.chromium.org/2069923004/diff/40001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/short-circuit.ll:4: ; REQUIRES: no_minimal_build
I think "REQUIRES: dump" might be more appropriate here

[manasijm, 2016-06-27 22:00:40]

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

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfg.cpp#newcode680
src/IceCfg.cpp:680: CfgVector<CfgNode *> Stack{Node};
On 2016/06/27 19:44:40, stichnot wrote:
> Can you use NodeList instead of CfgVector<CfgNode *> ?

Done.

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfg.cpp#newcode681
src/IceCfg.cpp:681: while(!Stack.empty()) {
On 2016/06/27 19:44:40, stichnot wrote:
> Please run "make format"...

Acknowledged.

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfg.cpp#newcode691
src/IceCfg.cpp:691: for (SizeT i = 0; i < NewList.size(); ++i) {
On 2016/06/27 19:44:41, stichnot wrote:
> I think it would be better to use a range-based for loop.
> 
> SizeT NodeIndex = 0;
> for (auto *Node : NewList) {
>   Node->resetIndex(NodeIndex++);
> }

Done.

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfg.cpp#newcode696
src/IceCfg.cpp:696: 
On 2016/06/27 19:44:40, stichnot wrote:
> just one blank line here

Done.

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1579: It++; // Have to split after the def
On 2016/06/27 19:44:41, stichnot wrote:
> ++It
> may be more efficient

Done.

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1585: NewNode->setName(getName().append("_2"));
On 2016/06/27 19:44:41, stichnot wrote:
> Wrap all the name management inside:
>   if (BuildDefs::dump()) { ... }

Done.

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1600: auto *Phi = llvm::dyn_cast<InstPhi>(&Inst);
On 2016/06/27 19:44:41, stichnot wrote:
> llvm::cast<>

Done.

https://codereview.chromium.org/2069923004/diff/40001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1622: appendInst(NewInst);
On 2016/06/27 19:44:41, stichnot wrote:
> Naively, it looks like there could be a path where NewInst==nullptr, which
would
> be bad.
> 
> I would add "assert(NewInst != nullptr);" here.

Done.

https://codereview.chromium.org/2069923004/diff/40001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/short-circuit.ll (right):

https://codereview.chromium.org/2069923004/diff/40001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/short-circuit.ll:4: ; REQUIRES: no_minimal_build
On 2016/06/27 19:44:41, stichnot wrote:
> I think "REQUIRES: dump" might be more appropriate here

allow_dump

[Jim Stichnoth, 2016-06-27 22:41:59]

https://codereview.chromium.org/2069923004/diff/60001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2069923004/diff/60001/src/IceCfg.cpp#newcode663
src/IceCfg.cpp:663: //(Similar logic for AND, jump to false instead of true
target.)
Can you add a space after the "//"?  I thought "make format" would do that but I
guess not.

https://codereview.chromium.org/2069923004/diff/60001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/2069923004/diff/60001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1588: 
There is trailing whitespace here (plus a couple other things in this file)
which "make format" should have taken care of.

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

https://codereview.chromium.org/2069923004/diff/60001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:563: 
I would remove this newline.

https://codereview.chromium.org/2069923004/diff/60001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/short-circuit.ll (right):

https://codereview.chromium.org/2069923004/diff/60001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/short-circuit.ll:1: ; Test on -enable-sc if basic
blocks are split when short circuit evaluation
remove trailing whitespace character

https://codereview.chromium.org/2069923004/diff/60001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/short-circuit.ll:14: define internal i32
@short_circuit(i32 %arg1, i32 %arg2, i32 %arg3, i32 %arg4,
remove trailing whitespace character

https://codereview.chromium.org/2069923004/diff/60001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/short-circuit.ll:42: ; CHECK:
.Lshort_circuit$target_false:
make sure the last line ends with a newline character

[manasijm, 2016-06-27 22:56:32]

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

https://codereview.chromium.org/2069923004/diff/60001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:563: 
On 2016/06/27 22:41:59, stichnot wrote:
> I would remove this newline.

Done.

https://codereview.chromium.org/2069923004/diff/60001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/short-circuit.ll (right):

https://codereview.chromium.org/2069923004/diff/60001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/short-circuit.ll:1: ; Test on -enable-sc if basic
blocks are split when short circuit evaluation
On 2016/06/27 22:41:59, stichnot wrote:
> remove trailing whitespace character

Done.

https://codereview.chromium.org/2069923004/diff/60001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/short-circuit.ll:14: define internal i32
@short_circuit(i32 %arg1, i32 %arg2, i32 %arg3, i32 %arg4,
On 2016/06/27 22:41:59, stichnot wrote:
> remove trailing whitespace character

Done.

https://codereview.chromium.org/2069923004/diff/60001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/short-circuit.ll:42: ; CHECK:
.Lshort_circuit$target_false:
On 2016/06/27 22:41:59, stichnot wrote:
> make sure the last line ends with a newline character

Done.

[Jim Stichnoth, 2016-06-27 23:02:33]

lgtm

[manasijm, 2016-06-27 23:12:40]

Description was changed from

==========
Short Circuit Evaluation

Split Nodes whenever an early jump is possible by short circuiting boolean
operations. Nodes are split after conservatively checking for side effects,
which include definition of multi block variables, function calls and
instructions involving memory.

BUG=None
==========

to

==========
Short Circuit Evaluation

Split Nodes whenever an early jump is possible by short circuiting boolean
operations. Nodes are split after conservatively checking for side effects,
which include definition of multi block variables, function calls and
instructions involving memory.

BUG=None
R=stichnot@chromium.org

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

[manasijm, 2016-06-27 23:12:41]

Committed patchset #5 (id:80001) manually as
45f51a2675e8367a2d7ce90e5b63e161da668856 (presubmit successful).