B3ReduceStrength::simplifyCFG() could do a lot more on each iteration
authorrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 19 Feb 2019 20:01:42 +0000 (20:01 +0000)
committerrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 19 Feb 2019 20:01:42 +0000 (20:01 +0000)
https://bugs.webkit.org/show_bug.cgi?id=194475

Reviewed by Saam Barati.

B3ReduceStrength::simplifyCFG() does three optimizations (which I will call A, B and C):
- A makes any terminal that points to a block that is empty except for a jump point to that jump's target instead.
- B transforms any branch or switch that points to a single block into a jump
- C finds blocks ending with jumps, whose successor has a single predecessor, and inline that successor block in place of the jump

It currently is limited in the following way:
- A and C can only fire once per block per iteration
- B can create jumps that would trigger A, but they may not be seen until the next iteration

Both problems are mitigated by going through the blocks in post-order, so that when a block is optimized most of its successors have already been optimized.
In a sense it is the symmetric of the peephole optimizer that goes in pre-order so that when an instruction is optimized most of its children have already been optimized.

On JetStream2 it reduces the average number of iterations from 3.35 to 3.24.

* b3/B3ReduceStrength.cpp:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@241768 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3ReduceStrength.cpp

index 6c2f025..48ae586 100644 (file)
@@ -1,3 +1,26 @@
+2019-02-19  Robin Morisset  <rmorisset@apple.com>
+
+        B3ReduceStrength::simplifyCFG() could do a lot more on each iteration
+        https://bugs.webkit.org/show_bug.cgi?id=194475
+
+        Reviewed by Saam Barati.
+
+        B3ReduceStrength::simplifyCFG() does three optimizations (which I will call A, B and C):
+        - A makes any terminal that points to a block that is empty except for a jump point to that jump's target instead.
+        - B transforms any branch or switch that points to a single block into a jump
+        - C finds blocks ending with jumps, whose successor has a single predecessor, and inline that successor block in place of the jump
+
+        It currently is limited in the following way:
+        - A and C can only fire once per block per iteration
+        - B can create jumps that would trigger A, but they may not be seen until the next iteration
+
+        Both problems are mitigated by going through the blocks in post-order, so that when a block is optimized most of its successors have already been optimized.
+        In a sense it is the symmetric of the peephole optimizer that goes in pre-order so that when an instruction is optimized most of its children have already been optimized.
+
+        On JetStream2 it reduces the average number of iterations from 3.35 to 3.24.
+
+        * b3/B3ReduceStrength.cpp:
+
 2019-02-19  Tadeu Zagallo  <tzagallo@apple.com>
 
         Move bytecode cache-related filesystem code out of CodeCache
index 7690b53..cea5144 100644 (file)
@@ -2376,7 +2376,7 @@ private:
         // predecessors during strength reduction since that minimizes the total number of fixpoint
         // iterations needed to kill a lot of code.
 
-        for (BasicBlock* block : m_proc) {
+        for (BasicBlock* block : m_proc.blocksInPostOrder()) {
             if (B3ReduceStrengthInternal::verbose)
                 dataLog("Considering block ", *block, ":\n");