The NaturalLoops algorithm only works when the list of blocks in a loop is de-duplicated
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 12 Jun 2018 05:05:09 +0000 (05:05 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 12 Jun 2018 05:05:09 +0000 (05:05 +0000)
commit2d2ed675e5c658700663fce80b0136329dbb46b0
tree40979413f01664f287c6eadaf1ec87cae9fc2a1f
parent83e988fa373359a3768c087c4679c00a4fa91d41
The NaturalLoops algorithm only works when the list of blocks in a loop is de-duplicated
https://bugs.webkit.org/show_bug.cgi?id=184829

Reviewed by Michael Saboff.

Source/JavaScriptCore:

This patch codifies that a BasicBlock's list of predecessors is de-duplicated.
In B3/Air, this just meant writing a validation rule. In DFG, this meant
ensuring this property when building up the predecessors list, and also adding
a validation rule. The NaturalLoops algorithm relies on this property.

* b3/B3Validate.cpp:
* b3/air/AirValidate.cpp:
* b3/testb3.cpp:
(JSC::B3::testLoopWithMultipleHeaderEdges):
(JSC::B3::run):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::handleSuccessor):
* dfg/DFGValidate.cpp:

Source/WTF:

This patch switches NaturalLoops to walking over a block's predecessors
instead of successors when building the initial list of loops and their
headers. The algorithm broke down when we had a footer block with multiple
control flow edges pointing to the same header. This made the loop data
structure contain multiple entries for the same basic block. The algorithm
breaks down when we end up in this state, since it means our way of detecting
what loop is more inner is broken, since that check uses a loop's size.

* wtf/NaturalLoops.h:
(WTF::NaturalLoop::addBlock):
(WTF::NaturalLoops::NaturalLoops):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@232741 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3Validate.cpp
Source/JavaScriptCore/b3/air/AirValidate.cpp
Source/JavaScriptCore/b3/testb3.cpp
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGValidate.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/NaturalLoops.h