Add an option to unfold short circuiting in AST.

Add an option to unfold short circuiting in AST.

We replace "a || b" with "a ? true : b",
"a && b" with "a ? b : false".

This is to work around short circuiting bug in Mac drivers.

ANGLEBUG=482
TEST=webgl conformance tests
R=alokp@chromium.org, kbr@chromium.org

Committed: https://code.google.com/p/angleproject/source/detail?r=5e70cf9

[Zhenyao Mo, 2013-10-09 18:23:20]

alokp, kbr: please review.
shannon, nicolas: fyi (feel free to review if you have time)

[Zhenyao Mo, 2013-10-09 18:25:28]

Instead of doing the rewrite on output stage, I tried in this CL to adjust the
AST tree.

I feel like this should be the general direction.  I also plan to move other
workarounds, like loop expansion, name hashing, out of the output stage.

[Alok Priyadarshi, 2013-10-09 23:12:48]

I do not like the fact that we are making a second traversal just to replace and
adding all the replacement functions on each type of node. I thought we were
thinking of maintaining a traversal stack which would enable us to do the
find-replace in one traversal.

https://codereview.appspot.com/14529048/diff/1010/include/GLSLANG/ShaderLang.h
File include/GLSLANG/ShaderLang.h (right):

https://codereview.appspot.com/14529048/diff/1010/include/GLSLANG/ShaderLang....
include/GLSLANG/ShaderLang.h:193: // This flag replace "a && b" with "a ? b :
false", "a || b" with
replace -> replaces. Put each replacement in separate lines for clarity. Also
add the motivation for doing so.

https://codereview.appspot.com/14529048/diff/1010/src/build_angle.gypi
File src/build_angle.gypi (right):

https://codereview.appspot.com/14529048/diff/1010/src/build_angle.gypi#newcode87
src/build_angle.gypi:87: 'compiler/UnfoldShortCircuitAST.cpp',
I do not see any need for the "AST" suffix.

https://codereview.appspot.com/14529048/diff/1010/src/compiler/UnfoldShortCir...
File src/compiler/UnfoldShortCircuitAST.cpp (right):

https://codereview.appspot.com/14529048/diff/1010/src/compiler/UnfoldShortCir...
src/compiler/UnfoldShortCircuitAST.cpp:12: TIntermSelection
*buildOrBinaryEquavalent(TIntermTyped *x, TIntermTyped *y)
Equavalent -> Equivalent.

May be a better name for this function would be UnfoldOR?

[kbr1, 2013-10-10 00:08:47]

I don't have a strong opinion on how to do the node replacements. In general,
updating the tree in the middle of traversal is tricky. If you replace the
current node -- or even worse, have to walk up the tree and modify the parent or
grandparent node -- you're in trouble.

In one compiler I worked on in the past, replacement of nodes was done
separately. During the traversal, new node sub-graphs were created for all
portions of the AST, and then in another pass, they were all swapped in. Let's
discuss this offline.

I'm not sure that adding a replace method is the best way to go. It would be
better if traverse() were generalized so that the visitor passed the parent node
and the address of the child node within that parent node into the traverser, so
that replacement could be done as its own TIntermTraverser without assistance of
a replaceChildNode helper.

https://codereview.appspot.com/14529048/diff/1010/src/compiler/IntermUpdater.h
File src/compiler/IntermUpdater.h (right):

https://codereview.appspot.com/14529048/diff/1010/src/compiler/IntermUpdater....
src/compiler/IntermUpdater.h:15: class IntermUpdater : public TIntermTraverser
Could a clearer name like "NodeUpdater" be used instead?

[Zhenyao Mo, 2013-10-10 22:36:46]

alokp, kbr: please take a look at this revised CL.

https://codereview.appspot.com/14529048/diff/1010/include/GLSLANG/ShaderLang.h
File include/GLSLANG/ShaderLang.h (right):

https://codereview.appspot.com/14529048/diff/1010/include/GLSLANG/ShaderLang....
include/GLSLANG/ShaderLang.h:193: // This flag replace "a && b" with "a ? b :
false", "a || b" with
On 2013/10/09 23:12:49, Alok Priyadarshi wrote:
> replace -> replaces. Put each replacement in separate lines for clarity. Also
> add the motivation for doing so.

Done.

https://codereview.appspot.com/14529048/diff/1010/src/build_angle.gypi
File src/build_angle.gypi (right):

https://codereview.appspot.com/14529048/diff/1010/src/build_angle.gypi#newcode87
src/build_angle.gypi:87: 'compiler/UnfoldShortCircuitAST.cpp',
On 2013/10/09 23:12:49, Alok Priyadarshi wrote:
> I do not see any need for the "AST" suffix.

the filename without AST already exists.

https://codereview.appspot.com/14529048/diff/1010/src/compiler/UnfoldShortCir...
File src/compiler/UnfoldShortCircuitAST.cpp (right):

https://codereview.appspot.com/14529048/diff/1010/src/compiler/UnfoldShortCir...
src/compiler/UnfoldShortCircuitAST.cpp:12: TIntermSelection
*buildOrBinaryEquavalent(TIntermTyped *x, TIntermTyped *y)
On 2013/10/09 23:12:49, Alok Priyadarshi wrote:
> Equavalent -> Equivalent.
> 
> May be a better name for this function would be UnfoldOR?

Done.

[Zhenyao Mo, 2013-10-10 22:55:09]

FYI: this is tested on Linux and Mac with webgl conformance and some webgl
demos.

Especially on MacOSX, the original failing
shader-with-short-circuiting-operators.html starts to pass with this CL.

[kbr1, 2013-10-10 23:28:12]

https://codereview.appspot.com/14529048/diff/14011/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.cpp (right):

https://codereview.appspot.com/14529048/diff/14011/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:61: // replaced before its ancester nodes
can be replace.
typos: ancester -> ancestor, replace -> replaced

https://codereview.appspot.com/14529048/diff/14011/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:62: // So we need to do the updates in
reverse order of traversing.
As we've discussed offline there are still bugs here. Please try to add a test
case showing this before fixing the bug.

[Zhenyao Mo, 2013-10-11 00:17:55]

Please take another review.

Also see the test case I added in the github webgl pull request.  Without this
fix, the test case failed on mac; with this fix, the test case passed.

Thanks for catching this!

https://codereview.appspot.com/14529048/diff/14011/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.cpp (right):

https://codereview.appspot.com/14529048/diff/14011/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:62: // So we need to do the updates in
reverse order of traversing.
On 2013/10/10 23:28:12, kbr1 wrote:
> As we've discussed offline there are still bugs here. Please try to add a test
> case showing this before fixing the bug.

Done.

[kbr1, 2013-10-11 00:51:47]

Nice work. LGTM

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.h (right):

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.h:45: // which are used to make the
replacements in the s
Incomplete comment.

[Alok Priyadarshi, 2013-10-11 03:28:34]

minor comments.

https://codereview.appspot.com/14529048/diff/16002/src/build_angle.gypi
File src/build_angle.gypi (right):

https://codereview.appspot.com/14529048/diff/16002/src/build_angle.gypi#newco...
src/build_angle.gypi:85: 'compiler/UnfoldShortCircuitAST.cpp',
nit: AST suffix is not necessary

https://codereview.appspot.com/14529048/diff/16002/src/compiler/Intermediate.cpp
File src/compiler/Intermediate.cpp (right):

https://codereview.appspot.com/14529048/diff/16002/src/compiler/Intermediate....
src/compiler/Intermediate.cpp:748: if (node == original) { \
can this be written as a template function instead?

https://codereview.appspot.com/14529048/diff/16002/src/compiler/Intermediate....
src/compiler/Intermediate.cpp:757: REPLACE_IF_IS(init, TIntermNode, original,
replacement);
we should return if rt == true after any of these replacements.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.cpp (right):

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:19: TIntermSelection *rt = new
TIntermSelection(x, trueNode, y, boolType);
no need to assign to rt.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:31: TIntermSelection *rt = new
TIntermSelection(x, y, falseNode, boolType);
no need to assign to rt.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:65: if (!entry.parent)
I think chrome style is to just crash.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:72: for (size_t jj = ii + 1; jj <
replacements.size(); ++jj)
please add a comment why this is necessary.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/intermediate.h
File src/compiler/intermediate.h (right):

https://codereview.appspot.com/14529048/diff/16002/src/compiler/intermediate....
src/compiler/intermediate.h:595: TIntermNode *getParent() { return path.size()
== 0 ? NULL : path.back(); }
getParentNode?

[Zhenyao Mo, 2013-10-11 22:21:57]

https://codereview.appspot.com/14529048/diff/16002/src/build_angle.gypi
File src/build_angle.gypi (right):

https://codereview.appspot.com/14529048/diff/16002/src/build_angle.gypi#newco...
src/build_angle.gypi:85: 'compiler/UnfoldShortCircuitAST.cpp',
On 2013/10/11 03:28:34, Alok Priyadarshi wrote:
> nit: AST suffix is not necessary

can't.  the filename without AST isn't avaiable.  See two lines below.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/Intermediate.cpp
File src/compiler/Intermediate.cpp (right):

https://codereview.appspot.com/14529048/diff/16002/src/compiler/Intermediate....
src/compiler/Intermediate.cpp:748: if (node == original) { \
On 2013/10/11 03:28:34, Alok Priyadarshi wrote:
> can this be written as a template function instead?

We can, but the code will no longer be one line per child.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/Intermediate....
src/compiler/Intermediate.cpp:757: REPLACE_IF_IS(init, TIntermNode, original,
replacement);
On 2013/10/11 03:28:34, Alok Priyadarshi wrote:
> we should return if rt == true after any of these replacements.

Done.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.cpp (right):

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:19: TIntermSelection *rt = new
TIntermSelection(x, trueNode, y, boolType);
On 2013/10/11 03:28:34, Alok Priyadarshi wrote:
> no need to assign to rt.

Done.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:31: TIntermSelection *rt = new
TIntermSelection(x, y, falseNode, boolType);
On 2013/10/11 03:28:34, Alok Priyadarshi wrote:
> no need to assign to rt.

Done.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:65: if (!entry.parent)
On 2013/10/11 03:28:34, Alok Priyadarshi wrote:
> I think chrome style is to just crash.

Done.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:72: for (size_t jj = ii + 1; jj <
replacements.size(); ++jj)
On 2013/10/11 03:28:34, Alok Priyadarshi wrote:
> please add a comment why this is necessary.

Done.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.h (right):

https://codereview.appspot.com/14529048/diff/16002/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.h:45: // which are used to make the
replacements in the s
On 2013/10/11 00:51:48, kbr1 wrote:
> Incomplete comment.

Done.

https://codereview.appspot.com/14529048/diff/16002/src/compiler/intermediate.h
File src/compiler/intermediate.h (right):

https://codereview.appspot.com/14529048/diff/16002/src/compiler/intermediate....
src/compiler/intermediate.h:595: TIntermNode *getParent() { return path.size()
== 0 ? NULL : path.back(); }
On 2013/10/11 03:28:34, Alok Priyadarshi wrote:
> getParentNode?

Done.

[Alok Priyadarshi, 2013-10-15 18:42:45]

lgtm. Please look at minor comments before committing.

https://codereview.appspot.com/14529048/diff/28001/src/compiler/Compiler.cpp
File src/compiler/Compiler.cpp (right):

https://codereview.appspot.com/14529048/diff/28001/src/compiler/Compiler.cpp#...
src/compiler/Compiler.cpp:201: unfoldShortCircuit.updateNodes();
nit: updateTree may be a better name?

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.cpp (right):

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:13: TIntermSelection
*UnfoldOR(TIntermTyped *x, TIntermTyped *y)
nit: * should be adjacent to TIntermSelection.

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:24: TIntermSelection
*UnfoldAND(TIntermTyped *x, TIntermTyped *y)
same here

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:61: for (size_t ii = 0; ii <
replacements.size(); ++ii)
nit: format 4 space indentation.

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.h (right):

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.h:23: struct NodeUpdateEntry
does this need to be public?

[Zhenyao Mo, 2013-10-15 19:58:16]

https://codereview.appspot.com/14529048/diff/28001/src/compiler/Compiler.cpp
File src/compiler/Compiler.cpp (right):

https://codereview.appspot.com/14529048/diff/28001/src/compiler/Compiler.cpp#...
src/compiler/Compiler.cpp:201: unfoldShortCircuit.updateNodes();
On 2013/10/15 18:42:45, Alok Priyadarshi wrote:
> nit: updateTree may be a better name?

Done.

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.cpp (right):

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:13: TIntermSelection
*UnfoldOR(TIntermTyped *x, TIntermTyped *y)
On 2013/10/15 18:42:45, Alok Priyadarshi wrote:
> nit: * should be adjacent to TIntermSelection.

Actually Angle style says * and & should be tight against the variable, not the
type.

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:24: TIntermSelection
*UnfoldAND(TIntermTyped *x, TIntermTyped *y)
On 2013/10/15 18:42:45, Alok Priyadarshi wrote:
> same here

same reply

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.cpp:61: for (size_t ii = 0; ii <
replacements.size(); ++ii)
On 2013/10/15 18:42:45, Alok Priyadarshi wrote:
> nit: format 4 space indentation.

Done.

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
File src/compiler/UnfoldShortCircuitAST.h (right):

https://codereview.appspot.com/14529048/diff/28001/src/compiler/UnfoldShortCi...
src/compiler/UnfoldShortCircuitAST.h:23: struct NodeUpdateEntry
On 2013/10/15 18:42:45, Alok Priyadarshi wrote:
> does this need to be public?

Done.

[Zhenyao Mo, 2013-10-15 19:59:37]

Committed patchset #5 manually as r5e70cf9 (presubmit successful).