69233 2011-10-02 18:32:47 -0700 DFG misses some obvious opportunities for common subexpression elimination 2011-10-02 19:12:32 -0700 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) All All RESOLVED FIXED P2 Normal --- 1 fpizlo webkit-unassigned oldest_to_newest 476744 0 fpizlo 2011-10-02 18:32:47 -0700 DFG CSE has some small issues: - It assumes that GetArrayLength is pure, even though it's not quite, since PutByVal can change the array length. - It assumes that a PutByVal changes structures, even though it doesn't. - It assumes that a PutByVal can affect property storage, even though it can't. - It assumes that a PutByOffset and PutStructure can affect array values, even though they can't. 476745 1 109433 fpizlo 2011-10-02 18:35:05 -0700 Created attachment 109433 the patch 476746 2 fpizlo 2011-10-02 18:37:28 -0700 Benchmark report for SunSpider, V8, and Kraken. VMs tested: "TipOfTree" at /Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc "BetterCSE" at /Volumes/Data/pizlo/septenary/OpenSource/WebKitBuild/Release/jsc Collected 30 samples per benchmark/VM, with 10 VM invocations per benchmark. Used 1 benchmark iteration per VM invocation for warm-up. Used the jsc-specific preciseTime() function to get microsecond-level timing. Reporting benchmark execution times with 95% confidence intervals in milliseconds. TipOfTree BetterCSE SunSpider: 3d-cube 7.5046+-0.1042 ? 7.5562+-0.1585 ? 3d-morph 7.5106+-0.0913 7.4168+-0.0906 might be 1.0127x faster 3d-raytrace 8.2949+-0.1256 8.2606+-0.1456 access-binary-trees 1.8232+-0.0648 1.8117+-0.0522 access-fannkuch 6.5405+-0.0993 6.4741+-0.0940 might be 1.0103x faster access-nbody 3.6042+-0.0701 3.5328+-0.0550 might be 1.0202x faster access-nsieve 2.6308+-0.0429 2.6169+-0.0398 bitops-3bit-bits-in-byte 1.7234+-0.0258 ? 1.7439+-0.0363 ? might be 1.0119x slower bitops-bits-in-byte 2.7558+-0.0494 ? 2.7863+-0.0448 ? might be 1.0110x slower bitops-bitwise-and 3.2326+-0.0454 ? 3.2411+-0.0434 ? bitops-nsieve-bits 5.3901+-0.0673 ? 5.4930+-0.0939 ? might be 1.0191x slower controlflow-recursive 2.0976+-0.0347 2.0861+-0.0318 crypto-aes 6.8874+-0.1255 ^ 6.6021+-0.1546 ^ definitely 1.0432x faster crypto-md5 2.8488+-0.0452 2.8352+-0.0489 crypto-sha1 2.5384+-0.0562 2.5211+-0.0491 date-format-tofte 10.1327+-0.1970 ? 10.1969+-0.1884 ? date-format-xparb 9.6255+-0.2156 9.3088+-0.1642 might be 1.0340x faster math-cordic 6.5242+-0.1773 6.2920+-0.0602 might be 1.0369x faster math-partial-sums 7.5976+-0.0878 7.5502+-0.0724 math-spectral-norm 2.9130+-0.0600 2.8608+-0.0540 might be 1.0182x faster regexp-dna 10.9628+-0.0961 10.9094+-0.1177 string-base64 5.5743+-0.0751 ? 5.6800+-0.1060 ? might be 1.0190x slower string-fasta 6.7034+-0.0966 6.6029+-0.0968 might be 1.0152x faster string-tagcloud 11.9118+-0.2269 11.8688+-0.2448 string-unpack-code 21.3631+-0.2577 21.2992+-0.2574 string-validate-input 6.3661+-0.1176 ? 6.3754+-0.1222 ? <arithmetic> * 6.3484+-0.0209 ^ 6.3047+-0.0168 ^ definitely 1.0069x faster <geometric> 5.2011+-0.0154 5.1695+-0.0167 <harmonic> 4.2598+-0.0216 4.2421+-0.0240 TipOfTree BetterCSE V8: crypto 72.4069+-0.4387 71.9852+-0.2791 deltablue 226.0043+-1.0641 225.5008+-1.1243 earley-boyer 87.9457+-0.3612 87.6738+-0.2001 raytrace 60.5582+-0.2882 ! 61.3586+-0.2842 ! definitely 1.0132x slower regexp 103.1425+-0.2652 ? 103.6629+-0.3114 ? richards 186.0587+-0.4058 ! 187.2996+-0.3897 ! definitely 1.0067x slower splay 90.7291+-0.3171 ? 90.9486+-0.2721 ? <arithmetic> 118.1208+-0.1917 ? 118.3471+-0.2055 ? <geometric> * 106.1333+-0.1626 ? 106.3785+-0.1427 ? <harmonic> 96.9275+-0.1764 ? 97.2004+-0.1431 ? TipOfTree BetterCSE Kraken: ai-astar 488.2833+-1.0508 ? 489.7596+-2.1248 ? audio-beat-detection 190.2345+-0.4833 189.9833+-0.7610 audio-dft 280.0364+-1.9020 279.1998+-1.6599 audio-fft 128.5120+-0.6387 ^ 125.7692+-0.3395 ^ definitely 1.0218x faster audio-oscillator 256.4819+-1.1002 ? 256.5966+-1.4991 ? imaging-darkroom 418.9083+-0.5420 ? 420.0696+-1.0855 ? imaging-desaturate 224.1991+-0.4250 224.1621+-0.6741 imaging-gaussian-blur 582.6255+-1.0266 ^ 580.6442+-0.8892 ^ definitely 1.0034x faster json-parse-financial 48.7130+-0.2418 ^ 48.0643+-0.1532 ^ definitely 1.0135x faster json-stringify-tinderbox 67.5046+-0.1666 ! 67.9862+-0.3144 ! definitely 1.0071x slower stanford-crypto-aes 130.5309+-1.0694 130.2505+-0.9259 stanford-crypto-ccm 101.3395+-0.3694 ? 101.8324+-0.6299 ? stanford-crypto-pbkdf2 194.0272+-1.1882 ? 195.6992+-1.0436 ? stanford-crypto-sha256-iterative 76.6602+-0.4262 76.3504+-0.2175 <arithmetic> * 227.7183+-0.3129 227.5977+-0.2831 <geometric> 177.2977+-0.2818 177.0157+-0.2768 <harmonic> 136.9826+-0.2585 136.5452+-0.2483 TipOfTree BetterCSE All benchmarks: <arithmetic> 88.9353+-0.1095 88.9089+-0.0849 <geometric> 23.3176+-0.0433 23.2360+-0.0452 <harmonic> 7.4864+-0.0371 7.4560+-0.0411 TipOfTree BetterCSE Geomean of preferred means: <scaled-result> 53.5343+-0.0684 53.4431+-0.0510 476748 3 fpizlo 2011-10-02 19:12:32 -0700 Landed in r96482. 109433 2011-10-02 18:35:05 -0700 2011-10-02 18:44:12 -0700 the patch bettercse_patch_1.diff text/plain 5789 fpizlo SW5kZXg6IFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9DaGFuZ2VMb2cKPT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291 cmNlL0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkocmV2aXNpb24gOTY0ODEpCisrKyBTb3VyY2Uv SmF2YVNjcmlwdENvcmUvQ2hhbmdlTG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMjAgQEAK KzIwMTEtMTAtMDIgIEZpbGlwIFBpemxvICA8ZnBpemxvQGFwcGxlLmNvbT4KKworICAgICAgICBE RkcgbWlzc2VzIHNvbWUgb2J2aW91cyBvcHBvcnR1bml0aWVzIGZvciBjb21tb24gc3ViZXhwcmVz c2lvbiBlbGltaW5hdGlvbgorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1 Zy5jZ2k/aWQ9NjkyMzMKKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKyAg ICAgICAgCisgICAgICAgIDAuNyUgc3BlZWQtdXAgb24gU3VuU3BpZGVyLgorCisgICAgICAgICog ZGZnL0RGR1Byb3BhZ2F0b3IuY3BwOgorICAgICAgICAoSlNDOjpERkc6OlByb3BhZ2F0b3I6Omdl dEJ5VmFsTG9hZEVsaW1pbmF0aW9uKToKKyAgICAgICAgKEpTQzo6REZHOjpQcm9wYWdhdG9yOjpn ZXRNZXRob2RMb2FkRWxpbWluYXRpb24pOgorICAgICAgICAoSlNDOjpERkc6OlByb3BhZ2F0b3I6 OmNoZWNrU3RydWN0dXJlTG9hZEVsaW1pbmF0aW9uKToKKyAgICAgICAgKEpTQzo6REZHOjpQcm9w YWdhdG9yOjpnZXRCeU9mZnNldExvYWRFbGltaW5hdGlvbik6CisgICAgICAgIChKU0M6OkRGRzo6 UHJvcGFnYXRvcjo6Z2V0UHJvcGVydHlTdG9yYWdlTG9hZEVsaW1pbmF0aW9uKToKKyAgICAgICAg KEpTQzo6REZHOjpQcm9wYWdhdG9yOjpwZXJmb3JtTm9kZUNTRSk6CisKIDIwMTEtMTAtMDIgIEdh dmluIEJhcnJhY2xvdWdoICA8YmFycmFjbG91Z2hAYXBwbGUuY29tPgogCiAgICAgICAgIEJ1ZyA2 NzQ1NSAtIERpZmZlcmVudCByZWd1bGFyIGV4cHJlc3Npb24gcmVzdWx0CkluZGV4OiBTb3VyY2Uv SmF2YVNjcmlwdENvcmUvZGZnL0RGR1Byb3BhZ2F0b3IuY3BwCj09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJj ZS9KYXZhU2NyaXB0Q29yZS9kZmcvREZHUHJvcGFnYXRvci5jcHAJKHJldmlzaW9uIDk2NDY0KQor KysgU291cmNlL0phdmFTY3JpcHRDb3JlL2RmZy9ERkdQcm9wYWdhdG9yLmNwcAkod29ya2luZyBj b3B5KQpAQCAtOTY0LDExICs5NjQsMTggQEAgcHJpdmF0ZToKICAgICAgICAgICAgICAgICBpZiAo bm9kZS5jaGlsZDEoKSA9PSBjaGlsZDEgJiYgY2Fub25pY2FsaXplKG5vZGUuY2hpbGQyKCkpID09 IGNhbm9uaWNhbGl6ZShjaGlsZDIpKQogICAgICAgICAgICAgICAgICAgICByZXR1cm4gbm9kZS5j aGlsZDMoKTsKICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgIGNhc2UgUHV0U3Ry dWN0dXJlOgorICAgICAgICAgICAgY2FzZSBQdXRCeU9mZnNldDoKKyAgICAgICAgICAgICAgICAv LyBHZXRCeVZhbCBjdXJyZW50bHkgYWx3YXlzIHNwZWN1bGF0ZXMgdGhhdCBpdCdzIGFjY2Vzc2lu ZyBhbgorICAgICAgICAgICAgICAgIC8vIGFycmF5IHdpdGggYW4gaW50ZWdlciBpbmRleCwgd2hp Y2ggbWVhbnMgdGhhdCBpdCdzIGltcG9zc2libGUKKyAgICAgICAgICAgICAgICAvLyBmb3IgYSBz dHJ1Y3R1cmUgY2hhbmdlIG9yIGEgcHV0IHRvIHByb3BlcnR5IHN0b3JhZ2UgdG8gYWZmZWN0Cisg ICAgICAgICAgICAgICAgLy8gdGhlIEdldEJ5VmFsLgorICAgICAgICAgICAgICAgIGJyZWFrOwog ICAgICAgICAgICAgZGVmYXVsdDoKKyAgICAgICAgICAgICAgICBpZiAoY2xvYmJlcnNXb3JsZChp bmRleCkpCisgICAgICAgICAgICAgICAgICAgIHJldHVybiBOb05vZGU7CiAgICAgICAgICAgICAg ICAgYnJlYWs7CiAgICAgICAgICAgICB9Ci0gICAgICAgICAgICBpZiAoY2xvYmJlcnNXb3JsZChp bmRleCkpCi0gICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgIH0KICAgICAgICAgcmV0dXJu IE5vTm9kZTsKICAgICB9CkBAIC05NzgsMTMgKzk4NSwzMCBAQCBwcml2YXRlOgogICAgICAgICBO b2RlSW5kZXggc3RhcnQgPSBzdGFydEluZGV4Rm9yQ2hpbGRyZW4oY2hpbGQxKTsKICAgICAgICAg Zm9yIChOb2RlSW5kZXggaW5kZXggPSBtX2NvbXBpbGVJbmRleDsgaW5kZXgtLSA+IHN0YXJ0Oykg ewogICAgICAgICAgICAgTm9kZSYgbm9kZSA9IG1fZ3JhcGhbaW5kZXhdOwotICAgICAgICAgICAg aWYgKG5vZGUub3AgPT0gQ2hlY2tNZXRob2QKLSAgICAgICAgICAgICAgICAmJiBub2RlLmNoaWxk MSgpID09IGNoaWxkMQotICAgICAgICAgICAgICAgICYmIG5vZGUuaWRlbnRpZmllck51bWJlcigp ID09IGlkZW50aWZpZXJOdW1iZXIKLSAgICAgICAgICAgICAgICAmJiBtX2dyYXBoLm1fbWV0aG9k Q2hlY2tEYXRhW25vZGUubWV0aG9kQ2hlY2tEYXRhSW5kZXgoKV0gPT0gbWV0aG9kQ2hlY2tEYXRh KQotICAgICAgICAgICAgICAgIHJldHVybiBpbmRleDsKLSAgICAgICAgICAgIGlmIChjbG9iYmVy c1dvcmxkKGluZGV4KSkKKyAgICAgICAgICAgIHN3aXRjaCAobm9kZS5vcCkgeworICAgICAgICAg ICAgY2FzZSBDaGVja01ldGhvZDoKKyAgICAgICAgICAgICAgICBpZiAobm9kZS5jaGlsZDEoKSA9 PSBjaGlsZDEKKyAgICAgICAgICAgICAgICAgICAgJiYgbm9kZS5pZGVudGlmaWVyTnVtYmVyKCkg PT0gaWRlbnRpZmllck51bWJlcgorICAgICAgICAgICAgICAgICAgICAmJiBtX2dyYXBoLm1fbWV0 aG9kQ2hlY2tEYXRhW25vZGUubWV0aG9kQ2hlY2tEYXRhSW5kZXgoKV0gPT0gbWV0aG9kQ2hlY2tE YXRhKQorICAgICAgICAgICAgICAgICAgICByZXR1cm4gaW5kZXg7CisgICAgICAgICAgICAgICAg YnJlYWs7CisgICAgICAgICAgICAgICAgCisgICAgICAgICAgICBjYXNlIFB1dEJ5T2Zmc2V0Ogor ICAgICAgICAgICAgICAgIC8vIElmIGEgcHV0IHdhcyBvcHRpbWl6ZWQgdG8gYnktb2Zmc2V0IHRo ZW4gaXQncyBub3QgY2hhbmdpbmcgdGhlIHN0cnVjdHVyZQorICAgICAgICAgICAgICAgIGJyZWFr OworICAgICAgICAgICAgICAgIAorICAgICAgICAgICAgY2FzZSBQdXRCeVZhbDoKKyAgICAgICAg ICAgIGNhc2UgUHV0QnlWYWxBbGlhczoKKyAgICAgICAgICAgICAgICAvLyBQdXRCeVZhbCBjdXJy ZW50bHkgYWx3YXlzIHNwZWN1bGF0ZXMgdGhhdCBpdCdzIGFjY2Vzc2luZyBhbiBhcnJheSB3aXRo IGFuCisgICAgICAgICAgICAgICAgLy8gaW50ZWdlciBpbmRleCwgd2hpY2ggbWVhbnMgdGhhdCBp dCdzIGltcG9zc2libGUgZm9yIGl0IHRvIGNhdXNlIGEgc3RydWN0dXJlCisgICAgICAgICAgICAg ICAgLy8gY2hhbmdlLgogICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgIAor ICAgICAgICAgICAgZGVmYXVsdDoKKyAgICAgICAgICAgICAgICBpZiAoY2xvYmJlcnNXb3JsZChp bmRleCkpCisgICAgICAgICAgICAgICAgICAgIHJldHVybiBOb05vZGU7CisgICAgICAgICAgICAg ICAgYnJlYWs7CisgICAgICAgICAgICB9CiAgICAgICAgIH0KICAgICAgICAgcmV0dXJuIE5vTm9k ZTsKICAgICB9CkBAIC0xMDExLDYgKzEwMzUsMTMgQEAgcHJpdmF0ZToKICAgICAgICAgICAgICAg ICAvLyBTZXR0aW5nIGEgcHJvcGVydHkgY2Fubm90IGNoYW5nZSB0aGUgc3RydWN0dXJlLgogICAg ICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgIAorICAgICAgICAgICAgY2FzZSBQ dXRCeVZhbDoKKyAgICAgICAgICAgIGNhc2UgUHV0QnlWYWxBbGlhczoKKyAgICAgICAgICAgICAg ICAvLyBQdXRCeVZhbCBjdXJyZW50bHkgYWx3YXlzIHNwZWN1bGF0ZXMgdGhhdCBpdCdzIGFjY2Vz c2luZyBhbiBhcnJheSB3aXRoIGFuCisgICAgICAgICAgICAgICAgLy8gaW50ZWdlciBpbmRleCwg d2hpY2ggbWVhbnMgdGhhdCBpdCdzIGltcG9zc2libGUgZm9yIGl0IHRvIGNhdXNlIGEgc3RydWN0 dXJlCisgICAgICAgICAgICAgICAgLy8gY2hhbmdlLgorICAgICAgICAgICAgICAgIGJyZWFrOwor ICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgZGVmYXVsdDoKICAgICAgICAgICAgICAgICBp ZiAoY2xvYmJlcnNXb3JsZChpbmRleCkpCiAgICAgICAgICAgICAgICAgICAgIHJldHVybiBmYWxz ZTsKQEAgLTEwNDQsNiArMTA3NSwxMyBAQCBwcml2YXRlOgogICAgICAgICAgICAgICAgIC8vIENo YW5naW5nIHRoZSBzdHJ1Y3R1cmUgY2Fubm90IGNoYW5nZSB0aGUgb3V0Y29tZSBvZiBhIHByb3Bl cnR5IGdldC4KICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAKKyAgICAg ICAgICAgIGNhc2UgUHV0QnlWYWw6CisgICAgICAgICAgICBjYXNlIFB1dEJ5VmFsQWxpYXM6Cisg ICAgICAgICAgICAgICAgLy8gUHV0QnlWYWwgY3VycmVudGx5IGFsd2F5cyBzcGVjdWxhdGVzIHRo YXQgaXQncyBhY2Nlc3NpbmcgYW4gYXJyYXkgd2l0aCBhbgorICAgICAgICAgICAgICAgIC8vIGlu dGVnZXIgaW5kZXgsIHdoaWNoIG1lYW5zIHRoYXQgaXQncyBpbXBvc3NpYmxlIGZvciBpdCB0byBj YXVzZSBhIHN0cnVjdHVyZQorICAgICAgICAgICAgICAgIC8vIGNoYW5nZS4KKyAgICAgICAgICAg ICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAKICAgICAgICAgICAgIGRlZmF1bHQ6CiAgICAg ICAgICAgICAgICAgaWYgKGNsb2JiZXJzV29ybGQoaW5kZXgpKQogICAgICAgICAgICAgICAgICAg ICByZXR1cm4gTm9Ob2RlOwpAQCAtMTA3MCw2ICsxMTA4LDEzIEBAIHByaXZhdGU6CiAgICAgICAg ICAgICAgICAgLy8gY2hhbmdlIHRoZSBwcm9wZXJ0eSBzdG9yYWdlIHBvaW50ZXIuCiAgICAgICAg ICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgCisgICAgICAgICAgICBjYXNlIFB1dEJ5 VmFsOgorICAgICAgICAgICAgY2FzZSBQdXRCeVZhbEFsaWFzOgorICAgICAgICAgICAgICAgIC8v IFB1dEJ5VmFsIGN1cnJlbnRseSBhbHdheXMgc3BlY3VsYXRlcyB0aGF0IGl0J3MgYWNjZXNzaW5n IGFuIGFycmF5IHdpdGggYW4KKyAgICAgICAgICAgICAgICAvLyBpbnRlZ2VyIGluZGV4LCB3aGlj aCBtZWFucyB0aGF0IGl0J3MgaW1wb3NzaWJsZSBmb3IgaXQgdG8gY2F1c2UgYSBzdHJ1Y3R1cmUK KyAgICAgICAgICAgICAgICAvLyBjaGFuZ2UuCisgICAgICAgICAgICAgICAgYnJlYWs7CisgICAg ICAgICAgICAgICAgCiAgICAgICAgICAgICBkZWZhdWx0OgogICAgICAgICAgICAgICAgIGlmIChj bG9iYmVyc1dvcmxkKGluZGV4KSkKICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIE5vTm9kZTsK QEAgLTExOTEsMTEgKzEyMzYsMTQgQEAgcHJpdmF0ZToKICAgICAgICAgY2FzZSBBcml0aE1heDoK ICAgICAgICAgY2FzZSBBcml0aFNxcnQ6CiAgICAgICAgIGNhc2UgR2V0Q2FsbGVlOgotICAgICAg ICBjYXNlIEdldEFycmF5TGVuZ3RoOgogICAgICAgICBjYXNlIEdldFN0cmluZ0xlbmd0aDoKICAg ICAgICAgICAgIHNldFJlcGxhY2VtZW50KHB1cmVDU0Uobm9kZSkpOwogICAgICAgICAgICAgYnJl YWs7CiAgICAgICAgICAgICAKKyAgICAgICAgY2FzZSBHZXRBcnJheUxlbmd0aDoKKyAgICAgICAg ICAgIHNldFJlcGxhY2VtZW50KGltcHVyZUNTRShub2RlKSk7CisgICAgICAgICAgICBicmVhazsK KyAgICAgICAgICAgIAogICAgICAgICBjYXNlIEdldFNjb3BlQ2hhaW46CiAgICAgICAgICAgICBz ZXRSZXBsYWNlbWVudChnZXRTY29wZUNoYWluTG9hZEVsaW1pbmF0aW9uKG5vZGUuc2NvcGVDaGFp bkRlcHRoKCkpKTsKICAgICAgICAgICAgIGJyZWFrOwo=