194475 2019-02-09 14:34:21 -0800 B3ReduceStrength::simplifyCFG() could do a lot more on each iteration 2019-02-19 12:02:42 -0800 1 1 1 Unclassified WebKit JavaScriptCore WebKit Nightly Build Unspecified Unspecified RESOLVED FIXED InRadar P2 Normal --- 194222 1 rmorisset rmorisset commit-queue ews-watchlist keith_miller mark.lam msaboff saam webkit-bug-importer oldest_to_newest 1504630 0 rmorisset 2019-02-09 14:34:21 -0800 B3ReduceStrength::simplifyCFG() does three optimizations (which I will call CFGa, CFGb and CFGc): - CFGa makes any terminal that points to a block empty except for a jump point to that jump instead. - CFGb transforms any branch or switch that point to a single block into a jump - CFGc inlines any block with a single predecessor that ends in a jump into the end of that predecessor. It currently is limited in the following way: - CFGa and CFGc can only fire once per block per iteration - CFGb can create jumps that would trigger CFGa, but they may not be seen until the next iteration I intend to fix the first problem simply by looping in CFGa and CFGc, and to mitigate the second problem by the simple expedient of optimizing the blocks in post-order, so when CFGa runs most successor blocks will already have been optimized (including by CFGb). 1504637 1 rmorisset 2019-02-09 15:25:24 -0800 Iterating on the blocks in postOrder reduces the number of iterations on average on JetStream2 from 3.35 to 3.24: Iterations Baseline PostOrder +Loop CFGa/c 1 164 165 167 2 554 557 551 3 1690 1931 1936 4 1626 1556 1545 5 309 159 167 6 46 24 26 7 9 7 7 8 1 0 0 9 0 0 0 10 0 0 0 On the other hand while looping CFGa and CFGc is profitable in isolation (numbers not shown above), the last column shows it brings nothing on top of iterating on the blocks in post-order. 1504640 2 361614 rmorisset 2019-02-09 15:31:38 -0800 Created attachment 361614 Patch 1504768 3 361614 saam 2019-02-10 19:35:04 -0800 Comment on attachment 361614 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=361614&action=review > Source/JavaScriptCore/ChangeLog:8 > + B3ReduceStrength::simplifyCFG() does three optimizations (which I will call CFGa, CFGb and CFGc): nit: just labeling these "A"/"B"/"C" is easier for readability IMO > Source/JavaScriptCore/ChangeLog:9 > + - CFGa makes any terminal that points to a block empty except for a jump point to that jump instead. This sentence confuses me. What's making a terminal "empty"? > Source/JavaScriptCore/ChangeLog:11 > + - CFGc inlines any block with a single predecessor that ends in a jump into the end of that predecessor. Doesn't this require the predecessor to have a single successor, and the successor to have a single predecessor? If I have a single predecessor, but that predecessor has two successors, I can't do this transformation. 1504906 4 361691 rmorisset 2019-02-11 10:23:48 -0800 Created attachment 361691 Patch 1504908 5 rmorisset 2019-02-11 10:26:58 -0800 Thanks for the review. (In reply to Saam Barati from comment #3) > Comment on attachment 361614 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=361614&action=review > > > Source/JavaScriptCore/ChangeLog:8 > > + B3ReduceStrength::simplifyCFG() does three optimizations (which I will call CFGa, CFGb and CFGc): > > nit: just labeling these "A"/"B"/"C" is easier for readability IMO Done. > > Source/JavaScriptCore/ChangeLog:9 > > + - CFGa makes any terminal that points to a block empty except for a jump point to that jump instead. > > This sentence confuses me. What's making a terminal "empty"? Sorry, I meant "a block that is empty". I fixed it, and tried to clarify the rest of the sentence. > > > Source/JavaScriptCore/ChangeLog:11 > > + - CFGc inlines any block with a single predecessor that ends in a jump into the end of that predecessor. > > Doesn't this require the predecessor to have a single successor, and the > successor to have a single predecessor? If I have a single predecessor, but > that predecessor has two successors, I can't do this transformation. I did not realize that my sentence was ambiguous: "that ends in a jump" was meant to apply to the predecessor (so that it indeed has a single successor). I've reworded it, please tell me if it is clearer. 1507737 6 361691 saam 2019-02-19 11:33:57 -0800 Comment on attachment 361691 Patch r=me 1507753 7 361691 commit-queue 2019-02-19 12:01:47 -0800 Comment on attachment 361691 Patch Clearing flags on attachment: 361691 Committed r241768: <https://trac.webkit.org/changeset/241768> 1507754 8 commit-queue 2019-02-19 12:01:49 -0800 All reviewed patches have been landed. Closing bug. 1507755 9 webkit-bug-importer 2019-02-19 12:02:42 -0800 <rdar://problem/48209346> 361614 2019-02-09 15:31:38 -0800 2019-02-11 10:23:47 -0800 Patch bug-194475-20190209153137.patch text/plain 2503 rmorisset U3VidmVyc2lvbiBSZXZpc2lvbjogMjQxMjQ1CmRpZmYgLS1naXQgYS9Tb3VyY2UvSmF2YVNjcmlw dENvcmUvQ2hhbmdlTG9nIGIvU291cmNlL0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwppbmRleCBj NmZlMGVhM2Q5Zjk1NjA4YzI3YjIzNzA0ZGI2ZjllZWQyYzEyNGFlLi45MGI4MTEwM2YzMmU0NmE3 ZWYwYWZlOTdmN2IwZTRmZjliOTRhY2Y1IDEwMDY0NAotLS0gYS9Tb3VyY2UvSmF2YVNjcmlwdENv cmUvQ2hhbmdlTG9nCisrKyBiL1NvdXJjZS9KYXZhU2NyaXB0Q29yZS9DaGFuZ2VMb2cKQEAgLTEs MyArMSwyNiBAQAorMjAxOS0wMi0wOSAgUm9iaW4gTW9yaXNzZXQgIDxybW9yaXNzZXRAYXBwbGUu Y29tPgorCisgICAgICAgIEIzUmVkdWNlU3RyZW5ndGg6OnNpbXBsaWZ5Q0ZHKCkgY291bGQgZG8g YSBsb3QgbW9yZSBvbiBlYWNoIGl0ZXJhdGlvbgorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0 Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9MTk0NDc1CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZ IChPT1BTISkuCisKKyAgICAgICAgQjNSZWR1Y2VTdHJlbmd0aDo6c2ltcGxpZnlDRkcoKSBkb2Vz IHRocmVlIG9wdGltaXphdGlvbnMgKHdoaWNoIEkgd2lsbCBjYWxsIENGR2EsIENGR2IgYW5kIENG R2MpOgorICAgICAgICAtIENGR2EgbWFrZXMgYW55IHRlcm1pbmFsIHRoYXQgcG9pbnRzIHRvIGEg YmxvY2sgZW1wdHkgZXhjZXB0IGZvciBhIGp1bXAgcG9pbnQgdG8gdGhhdCBqdW1wIGluc3RlYWQu CisgICAgICAgIC0gQ0ZHYiB0cmFuc2Zvcm1zIGFueSBicmFuY2ggb3Igc3dpdGNoIHRoYXQgcG9p bnQgdG8gYSBzaW5nbGUgYmxvY2sgaW50byBhIGp1bXAKKyAgICAgICAgLSBDRkdjIGlubGluZXMg YW55IGJsb2NrIHdpdGggYSBzaW5nbGUgcHJlZGVjZXNzb3IgdGhhdCBlbmRzIGluIGEganVtcCBp bnRvIHRoZSBlbmQgb2YgdGhhdCBwcmVkZWNlc3Nvci4KKworICAgICAgICBJdCBjdXJyZW50bHkg aXMgbGltaXRlZCBpbiB0aGUgZm9sbG93aW5nIHdheToKKyAgICAgICAgLSBDRkdhIGFuZCBDRkdj IGNhbiBvbmx5IGZpcmUgb25jZSBwZXIgYmxvY2sgcGVyIGl0ZXJhdGlvbgorICAgICAgICAtIENG R2IgY2FuIGNyZWF0ZSBqdW1wcyB0aGF0IHdvdWxkIHRyaWdnZXIgQ0ZHYSwgYnV0IHRoZXkgbWF5 IG5vdCBiZSBzZWVuIHVudGlsIHRoZSBuZXh0IGl0ZXJhdGlvbgorCisgICAgICAgIEJvdGggcHJv YmxlbXMgYXJlIG1pdGlnYXRlZCBieSBnb2luZyB0aHJvdWdoIHRoZSBibG9ja3MgaW4gcG9zdC1v cmRlciwgc28gdGhhdCB3aGVuIGEgYmxvY2sgaXMgb3B0aW1pemVkIG1vc3Qgb2YgaXRzIHN1Y2Nl c3NvcnMgaGF2ZSBhbHJlYWR5IGJlZW4gb3B0aW1pemVkLgorICAgICAgICBJbiBhIHNlbnNlIGl0 IGlzIHRoZSBzeW1tZXRyaWMgb2YgdGhlIHBlZXBob2xlIG9wdGltaXplciB0aGF0IGdvZXMgaW4g cHJlLW9yZGVyIHNvIHRoYXQgd2hlbiBhbiBpbnN0cnVjdGlvbiBpcyBvcHRpbWl6ZWQgbW9zdCBv ZiBpdHMgY2hpbGRyZW4gaGF2ZSBhbHJlYWR5IGJlZW4gb3B0aW1pemVkLgorCisgICAgICAgIE9u IEpldFN0cmVhbTIgaXQgcmVkdWNlcyB0aGUgYXZlcmFnZSBudW1iZXIgb2YgaXRlcmF0aW9ucyBm cm9tIDMuMzUgdG8gMy4yNC4KKworICAgICAgICAqIGIzL0IzUmVkdWNlU3RyZW5ndGguY3BwOgor CiAyMDE5LTAyLTA5ICBEYXJpbiBBZGxlciAgPGRhcmluQGFwcGxlLmNvbT4KIAogICAgICAgICBF bGltaW5hdGUgdW5uZWNlc3NhcnkgU3RyaW5nIHRlbXBvcmFyaWVzIGJ5IHVzaW5nIFN0cmluZ0Nv bmNhdGVuYXRlTnVtYmVycwpkaWZmIC0tZ2l0IGEvU291cmNlL0phdmFTY3JpcHRDb3JlL2IzL0Iz UmVkdWNlU3RyZW5ndGguY3BwIGIvU291cmNlL0phdmFTY3JpcHRDb3JlL2IzL0IzUmVkdWNlU3Ry ZW5ndGguY3BwCmluZGV4IDc2OTBiNTNkZThkOWY1NTdmNzExOGFmZGIwY2FkMmUxYTZhMmNjYmIu LmNlYTUxNDQzYmViN2MzOWI5ZWRhNzI3YjViYTYxMjcyOGRiMDgzN2MgMTAwNjQ0Ci0tLSBhL1Nv dXJjZS9KYXZhU2NyaXB0Q29yZS9iMy9CM1JlZHVjZVN0cmVuZ3RoLmNwcAorKysgYi9Tb3VyY2Uv SmF2YVNjcmlwdENvcmUvYjMvQjNSZWR1Y2VTdHJlbmd0aC5jcHAKQEAgLTIzNzYsNyArMjM3Niw3 IEBAIHByaXZhdGU6CiAgICAgICAgIC8vIHByZWRlY2Vzc29ycyBkdXJpbmcgc3RyZW5ndGggcmVk dWN0aW9uIHNpbmNlIHRoYXQgbWluaW1pemVzIHRoZSB0b3RhbCBudW1iZXIgb2YgZml4cG9pbnQK ICAgICAgICAgLy8gaXRlcmF0aW9ucyBuZWVkZWQgdG8ga2lsbCBhIGxvdCBvZiBjb2RlLgogCi0g ICAgICAgIGZvciAoQmFzaWNCbG9jayogYmxvY2sgOiBtX3Byb2MpIHsKKyAgICAgICAgZm9yIChC YXNpY0Jsb2NrKiBibG9jayA6IG1fcHJvYy5ibG9ja3NJblBvc3RPcmRlcigpKSB7CiAgICAgICAg ICAgICBpZiAoQjNSZWR1Y2VTdHJlbmd0aEludGVybmFsOjp2ZXJib3NlKQogICAgICAgICAgICAg ICAgIGRhdGFMb2coIkNvbnNpZGVyaW5nIGJsb2NrICIsICpibG9jaywgIjpcbiIpOwogCg== 361691 2019-02-11 10:23:48 -0800 2019-02-19 12:01:47 -0800 Patch bug-194475-20190211102347.patch text/plain 2410 rmorisset SW5kZXg6IFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9DaGFuZ2VMb2cKPT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291 cmNlL0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkocmV2aXNpb24gMjQxMjY3KQorKysgU291cmNl L0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDI2IEBA CisyMDE5LTAyLTExICBSb2JpbiBNb3Jpc3NldCAgPHJtb3Jpc3NldEBhcHBsZS5jb20+CisKKyAg ICAgICAgQjNSZWR1Y2VTdHJlbmd0aDo6c2ltcGxpZnlDRkcoKSBjb3VsZCBkbyBhIGxvdCBtb3Jl IG9uIGVhY2ggaXRlcmF0aW9uCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3df YnVnLmNnaT9pZD0xOTQ0NzUKKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4K KworICAgICAgICBCM1JlZHVjZVN0cmVuZ3RoOjpzaW1wbGlmeUNGRygpIGRvZXMgdGhyZWUgb3B0 aW1pemF0aW9ucyAod2hpY2ggSSB3aWxsIGNhbGwgQSwgQiBhbmQgQyk6CisgICAgICAgIC0gQSBt YWtlcyBhbnkgdGVybWluYWwgdGhhdCBwb2ludHMgdG8gYSBibG9jayB0aGF0IGlzIGVtcHR5IGV4 Y2VwdCBmb3IgYSBqdW1wIHBvaW50IHRvIHRoYXQganVtcCdzIHRhcmdldCBpbnN0ZWFkLgorICAg ICAgICAtIEIgdHJhbnNmb3JtcyBhbnkgYnJhbmNoIG9yIHN3aXRjaCB0aGF0IHBvaW50cyB0byBh IHNpbmdsZSBibG9jayBpbnRvIGEganVtcAorICAgICAgICAtIEMgZmluZHMgYmxvY2tzIGVuZGlu ZyB3aXRoIGp1bXBzLCB3aG9zZSBzdWNjZXNzb3IgaGFzIGEgc2luZ2xlIHByZWRlY2Vzc29yLCBh bmQgaW5saW5lIHRoYXQgc3VjY2Vzc29yIGJsb2NrIGluIHBsYWNlIG9mIHRoZSBqdW1wCisKKyAg ICAgICAgSXQgY3VycmVudGx5IGlzIGxpbWl0ZWQgaW4gdGhlIGZvbGxvd2luZyB3YXk6CisgICAg ICAgIC0gQSBhbmQgQyBjYW4gb25seSBmaXJlIG9uY2UgcGVyIGJsb2NrIHBlciBpdGVyYXRpb24K KyAgICAgICAgLSBCIGNhbiBjcmVhdGUganVtcHMgdGhhdCB3b3VsZCB0cmlnZ2VyIEEsIGJ1dCB0 aGV5IG1heSBub3QgYmUgc2VlbiB1bnRpbCB0aGUgbmV4dCBpdGVyYXRpb24KKworICAgICAgICBC b3RoIHByb2JsZW1zIGFyZSBtaXRpZ2F0ZWQgYnkgZ29pbmcgdGhyb3VnaCB0aGUgYmxvY2tzIGlu IHBvc3Qtb3JkZXIsIHNvIHRoYXQgd2hlbiBhIGJsb2NrIGlzIG9wdGltaXplZCBtb3N0IG9mIGl0 cyBzdWNjZXNzb3JzIGhhdmUgYWxyZWFkeSBiZWVuIG9wdGltaXplZC4KKyAgICAgICAgSW4gYSBz ZW5zZSBpdCBpcyB0aGUgc3ltbWV0cmljIG9mIHRoZSBwZWVwaG9sZSBvcHRpbWl6ZXIgdGhhdCBn b2VzIGluIHByZS1vcmRlciBzbyB0aGF0IHdoZW4gYW4gaW5zdHJ1Y3Rpb24gaXMgb3B0aW1pemVk IG1vc3Qgb2YgaXRzIGNoaWxkcmVuIGhhdmUgYWxyZWFkeSBiZWVuIG9wdGltaXplZC4KKworICAg ICAgICBPbiBKZXRTdHJlYW0yIGl0IHJlZHVjZXMgdGhlIGF2ZXJhZ2UgbnVtYmVyIG9mIGl0ZXJh dGlvbnMgZnJvbSAzLjM1IHRvIDMuMjQuCisKKyAgICAgICAgKiBiMy9CM1JlZHVjZVN0cmVuZ3Ro LmNwcDoKKwogMjAxOS0wMi0xMCAgTWFyayBMYW0gIDxtYXJrLmxhbUBhcHBsZS5jb20+CiAKICAg ICAgICAgUmVtb3ZlIHRoZSBSRUxFQVNFX0FTU0VSVCBjaGVjayBmb3IgZHVwbGljYXRlIGNhc2Vz IGluIHRoZSBCaW5hcnlTd2l0Y2ggY29uc3RydWN0b3IuCkluZGV4OiBTb3VyY2UvSmF2YVNjcmlw dENvcmUvYjMvQjNSZWR1Y2VTdHJlbmd0aC5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291cmNlL0phdmFT Y3JpcHRDb3JlL2IzL0IzUmVkdWNlU3RyZW5ndGguY3BwCShyZXZpc2lvbiAyNDEyNjcpCisrKyBT b3VyY2UvSmF2YVNjcmlwdENvcmUvYjMvQjNSZWR1Y2VTdHJlbmd0aC5jcHAJKHdvcmtpbmcgY29w eSkKQEAgLTIzNzYsNyArMjM3Niw3IEBAIHByaXZhdGU6CiAgICAgICAgIC8vIHByZWRlY2Vzc29y cyBkdXJpbmcgc3RyZW5ndGggcmVkdWN0aW9uIHNpbmNlIHRoYXQgbWluaW1pemVzIHRoZSB0b3Rh bCBudW1iZXIgb2YgZml4cG9pbnQKICAgICAgICAgLy8gaXRlcmF0aW9ucyBuZWVkZWQgdG8ga2ls bCBhIGxvdCBvZiBjb2RlLgogCi0gICAgICAgIGZvciAoQmFzaWNCbG9jayogYmxvY2sgOiBtX3By b2MpIHsKKyAgICAgICAgZm9yIChCYXNpY0Jsb2NrKiBibG9jayA6IG1fcHJvYy5ibG9ja3NJblBv c3RPcmRlcigpKSB7CiAgICAgICAgICAgICBpZiAoQjNSZWR1Y2VTdHJlbmd0aEludGVybmFsOjp2 ZXJib3NlKQogICAgICAgICAgICAgICAgIGRhdGFMb2coIkNvbnNpZGVyaW5nIGJsb2NrICIsICpi bG9jaywgIjpcbiIpOwogCg==