added basic dataflow analysis to skslc

added basic dataflow analysis to skslc

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2405383003

Committed: https://skia.googlesource.com/skia/+/22f939e849013b7fc51374c289b5bf37e63dfdb1

[ethannicholas, 2016-10-12 14:36:11]

Description was changed from

==========
added basic dataflow analysis to skslc

BUG=skia:
==========

to

==========
added basic dataflow analysis to skslc

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2405383003
==========

[ethannicholas, 2016-10-12 20:28:36]

ethannicholas@google.com changed reviewers:
+ benjaminwagner@google.com

[dogben, 2016-10-13 03:55:41]

benjaminwagner@google.com changed reviewers:
+ bsalomon@google.com

[dogben, 2016-10-13 03:55:43]

Adding bsalomon for tests/PrimitiveProcessorTest.cpp and src/gpu/effects/*,
because I don't understand what that's about.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
File src/sksl/SkSLCFGGenerator.cpp (right):

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:44: if (from == 0 ||
fBlocks[from].fEntrances.size()) {
I don't understand this, and the documentation doesn't mention anything about
it.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:93: cfg.addExit(start, cfg.fCurrent);
Missing cfg.newBlock().

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:136: this->addExpression(cfg, ((const
IndexExpression*) e)->fIndex.get());
nit: Probably doesn't matter much, but SPIRV generator evaluates fBase before
fIndex.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:184: break;
Need this->addLValue(cfg, ((const FieldAccess*) e)->fBase.get());

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:186: this->addExpression(cfg, ((const
IndexExpression*) e)->fIndex.get());
Need this->addLValue(cfg, ((const IndexExpression*) e)->fBase.get());

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:189: break;
Need this->addLValue(cfg, ((const Swizzle*) e)->fBase.get());

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:229: cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
BasicBlock::Node::kStatement_Kind, s });
Need addExpression for each variable's value.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:233: cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
BasicBlock::Node::kStatement_Kind, s });
Need addExpression for return value.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:322: }
nit: // namespace

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
File src/sksl/SkSLCFGGenerator.h (right):

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.h:19: typedef size_t BlockId;
nit: document this is index in CFG::fBlocks.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.h:69: CFG getCFG(const FunctionDefinition& f);
nit: mention getCFG does not set BasicBlock::fBefore

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.cpp
File src/sksl/SkSLCompiler.cpp (right):

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.c...
src/sksl/SkSLCompiler.cpp:222: for (auto iter = block.fExits.begin(); iter !=
block.fExits.end(); iter++) {
nit: range loop would be easier to understand. Same for afterIter.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.c...
src/sksl/SkSLCompiler.cpp:311: if (cfg.fStart != cfg.fExit &&
cfg.fBlocks[cfg.fExit].fEntrances.size()) {
nit: It's always true that fStart != fExit, because getCFG creates a different
block for each.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLIRGenerato...
File src/sksl/SkSLIRGenerator.cpp (right):

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLIRGenerato...
src/sksl/SkSLIRGenerator.cpp:262: initializer = nullptr;
nit: unneeded

x3

https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp
File tests/SkSLErrorTest.cpp (right):

https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp...
tests/SkSLErrorTest.cpp:284: "void main() { int x; if (5 == 2) x = 3; x++; }",
Would be good to add a few more test cases:

1. expressions in lvalues:
void main() {
    int x[2][2];
    x[i][1] = 4;
}

2. expressions in return statement:
int main() { return x; }

3. expressions in variable assignments:
void main() { int x = y; }

4. logical and and or
void main() { if (true && (false || x)) { return; } }

https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp...
tests/SkSLErrorTest.cpp:299: "void main() { if (true) return; else discard;
return; }",
Maybe add this test case: (I think this works correctly, but I originally
thought it didn't work.)
void main() {
    return;
    while (true);
}

[bsalomon, 2016-10-13 13:49:41]

On 2016/10/13 03:55:43, dogben wrote:
> Adding bsalomon for tests/PrimitiveProcessorTest.cpp and src/gpu/effects/*,
> because I don't understand what that's about.

that lgtm

> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> File src/sksl/SkSLCFGGenerator.cpp (right):
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:44: if (from == 0 ||
> fBlocks[from].fEntrances.size()) {
> I don't understand this, and the documentation doesn't mention anything about
> it.
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:93: cfg.addExit(start, cfg.fCurrent);
> Missing cfg.newBlock().
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:136: this->addExpression(cfg, ((const
> IndexExpression*) e)->fIndex.get());
> nit: Probably doesn't matter much, but SPIRV generator evaluates fBase before
> fIndex.
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:184: break;
> Need this->addLValue(cfg, ((const FieldAccess*) e)->fBase.get());
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:186: this->addExpression(cfg, ((const
> IndexExpression*) e)->fIndex.get());
> Need this->addLValue(cfg, ((const IndexExpression*) e)->fBase.get());
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:189: break;
> Need this->addLValue(cfg, ((const Swizzle*) e)->fBase.get());
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:229:
cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
> BasicBlock::Node::kStatement_Kind, s });
> Need addExpression for each variable's value.
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:233:
cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
> BasicBlock::Node::kStatement_Kind, s });
> Need addExpression for return value.
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.cpp:322: }
> nit: // namespace
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> File src/sksl/SkSLCFGGenerator.h (right):
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.h:19: typedef size_t BlockId;
> nit: document this is index in CFG::fBlocks.
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
> src/sksl/SkSLCFGGenerator.h:69: CFG getCFG(const FunctionDefinition& f);
> nit: mention getCFG does not set BasicBlock::fBefore
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.cpp
> File src/sksl/SkSLCompiler.cpp (right):
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.c...
> src/sksl/SkSLCompiler.cpp:222: for (auto iter = block.fExits.begin(); iter !=
> block.fExits.end(); iter++) {
> nit: range loop would be easier to understand. Same for afterIter.
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.c...
> src/sksl/SkSLCompiler.cpp:311: if (cfg.fStart != cfg.fExit &&
> cfg.fBlocks[cfg.fExit].fEntrances.size()) {
> nit: It's always true that fStart != fExit, because getCFG creates a different
> block for each.
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLIRGenerato...
> File src/sksl/SkSLIRGenerator.cpp (right):
> 
>
https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLIRGenerato...
> src/sksl/SkSLIRGenerator.cpp:262: initializer = nullptr;
> nit: unneeded
> 
> x3
> 
> https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp
> File tests/SkSLErrorTest.cpp (right):
> 
>
https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp...
> tests/SkSLErrorTest.cpp:284: "void main() { int x; if (5 == 2) x = 3; x++; }",
> Would be good to add a few more test cases:
> 
> 1. expressions in lvalues:
> void main() {
>     int x[2][2];
>     x[i][1] = 4;
> }
> 
> 2. expressions in return statement:
> int main() { return x; }
> 
> 3. expressions in variable assignments:
> void main() { int x = y; }
> 
> 4. logical and and or
> void main() { if (true && (false || x)) { return; } }
> 
>
https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp...
> tests/SkSLErrorTest.cpp:299: "void main() { if (true) return; else discard;
> return; }",
> Maybe add this test case: (I think this works correctly, but I originally
> thought it didn't work.)
> void main() {
>     return;
>     while (true);
> }

[ethannicholas, 2016-10-13 17:41:28]

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
File src/sksl/SkSLCFGGenerator.cpp (right):

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:44: if (from == 0 ||
fBlocks[from].fEntrances.size()) {
On 2016/10/13 03:55:43, dogben wrote:
> I don't understand this, and the documentation doesn't mention anything about
> it.

Added a comment explaining it.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:93: cfg.addExit(start, cfg.fCurrent);
On 2016/10/13 03:55:42, dogben wrote:
> Missing cfg.newBlock().

Fixed.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:136: this->addExpression(cfg, ((const
IndexExpression*) e)->fIndex.get());
On 2016/10/13 03:55:43, dogben wrote:
> nit: Probably doesn't matter much, but SPIRV generator evaluates fBase before
> fIndex.

Probably doesn't matter, but I fixed it anyway :-).

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:184: break;
On 2016/10/13 03:55:43, dogben wrote:
> Need this->addLValue(cfg, ((const FieldAccess*) e)->fBase.get());

I was initially thinking that would never do anything, since surely it's just
going to be a variable reference, but of course you could write (a = b).xy =
foo; (ugh)

Good catch.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:229: cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
BasicBlock::Node::kStatement_Kind, s });
On 2016/10/13 03:55:43, dogben wrote:
> Need addExpression for each variable's value.

Done.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:233: cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
BasicBlock::Node::kStatement_Kind, s });
On 2016/10/13 03:55:43, dogben wrote:
> Need addExpression for return value.

Done.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:322: }
On 2016/10/13 03:55:43, dogben wrote:
> nit: // namespace

Fixed.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.cpp
File src/sksl/SkSLCompiler.cpp (right):

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.c...
src/sksl/SkSLCompiler.cpp:222: for (auto iter = block.fExits.begin(); iter !=
block.fExits.end(); iter++) {
On 2016/10/13 03:55:43, dogben wrote:
> nit: range loop would be easier to understand. Same for afterIter.

Fixed.

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLCompiler.c...
src/sksl/SkSLCompiler.cpp:311: if (cfg.fStart != cfg.fExit &&
cfg.fBlocks[cfg.fExit].fEntrances.size()) {
On 2016/10/13 03:55:43, dogben wrote:
> nit: It's always true that fStart != fExit, because getCFG creates a different
> block for each.

Well, it wasn't true when I wrote that! Fixed :-)

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLIRGenerato...
File src/sksl/SkSLIRGenerator.cpp (right):

https://codereview.chromium.org/2405383003/diff/20001/src/sksl/SkSLIRGenerato...
src/sksl/SkSLIRGenerator.cpp:262: initializer = nullptr;
On 2016/10/13 03:55:43, dogben wrote:
> nit: unneeded
> 
> x3

Fixed.

https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp
File tests/SkSLErrorTest.cpp (right):

https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp...
tests/SkSLErrorTest.cpp:284: "void main() { int x; if (5 == 2) x = 3; x++; }",
On 2016/10/13 03:55:43, dogben wrote:
> Would be good to add a few more test cases:
> 
> 1. expressions in lvalues:
> void main() {
>     int x[2][2];
>     x[i][1] = 4;
> }
> 
> 2. expressions in return statement:
> int main() { return x; }
> 
> 3. expressions in variable assignments:
> void main() { int x = y; }
> 
> 4. logical and and or
> void main() { if (true && (false || x)) { return; } }

Done.

https://codereview.chromium.org/2405383003/diff/20001/tests/SkSLErrorTest.cpp...
tests/SkSLErrorTest.cpp:299: "void main() { if (true) return; else discard;
return; }",
On 2016/10/13 03:55:43, dogben wrote:
> Maybe add this test case: (I think this works correctly, but I originally
> thought it didn't work.)
> void main() {
>     return;
>     while (true);
> }

Done.

[ethannicholas, 2016-10-13 17:49:48]

The CQ bit was checked by ethannicholas@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-10-13 17:49:51]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-13 17:55:41]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-13 17:55:42]

Dry run: Try jobs failed on following builders:
  Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Debug-GN-Trybot on master.client.skia
(JOB_FAILED,
http://build.chromium.org/p/client.skia/builders/Test-Ubuntu-GCC-GCE-CPU-AVX2...)

[ethannicholas, 2016-10-13 19:04:43]

The CQ bit was checked by ethannicholas@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-10-13 19:04:55]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[dogben, 2016-10-13 19:12:43]

https://codereview.chromium.org/2405383003/diff/40001/src/sksl/SkSLCFGGenerat...
File src/sksl/SkSLCFGGenerator.cpp (right):

https://codereview.chromium.org/2405383003/diff/40001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:240: vd.fValue.get()
I'm pretty sure you need this->addExpression(cfg, vd.fValue.get()), because the
expression could be/contain a ternary expression (or I suppose a logical and or
or).

https://codereview.chromium.org/2405383003/diff/60001/tests/SkSLErrorTest.cpp
File tests/SkSLErrorTest.cpp (right):

https://codereview.chromium.org/2405383003/diff/60001/tests/SkSLErrorTest.cpp...
tests/SkSLErrorTest.cpp:293: "void main() { int x; int y; x = y; }",
nit: I mentioned this case for the var declaration case, i.e.
int x;
int y = x;

[commit-bot: I haz the power, 2016-10-13 19:37:44]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-13 19:37:45]

Dry run: This issue passed the CQ dry run.

[ethannicholas, 2016-10-13 19:42:06]

https://codereview.chromium.org/2405383003/diff/40001/src/sksl/SkSLCFGGenerat...
File src/sksl/SkSLCFGGenerator.cpp (right):

https://codereview.chromium.org/2405383003/diff/40001/src/sksl/SkSLCFGGenerat...
src/sksl/SkSLCFGGenerator.cpp:240: vd.fValue.get()
On 2016/10/13 19:12:43, dogben wrote:
> I'm pretty sure you need this->addExpression(cfg, vd.fValue.get()), because
the
> expression could be/contain a ternary expression (or I suppose a logical and
or
> or).

I have absolutely no idea what I was thinking there.

[dogben, 2016-10-13 19:53:01]

lgtm

[ethannicholas, 2016-10-13 19:53:34]

The CQ bit was checked by ethannicholas@google.com

[ethannicholas, 2016-10-13 19:53:35]

The patchset sent to the CQ was uploaded after l-g-t-m from bsalomon@google.com
Link to the patchset: https://codereview.chromium.org/2405383003/#ps80001
(title: "I have no idea what I was thinking")

[commit-bot: I haz the power, 2016-10-13 19:53:46]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-13 20:25:37]

Description was changed from

==========
added basic dataflow analysis to skslc

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2405383003
==========

to

==========
added basic dataflow analysis to skslc

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2405383003

Committed:
https://skia.googlesource.com/skia/+/22f939e849013b7fc51374c289b5bf37e63dfdb1
==========

[commit-bot: I haz the power, 2016-10-13 20:25:38]

Committed patchset #5 (id:80001) as
https://skia.googlesource.com/skia/+/22f939e849013b7fc51374c289b5bf37e63dfdb1