Bug 69233

Summary: DFG misses some obvious opportunities for common subexpression elimination
Product: WebKit Reporter: Filip Pizlo <fpizlo>
Component: JavaScriptCoreAssignee: Nobody <webkit-unassigned>
Status: RESOLVED FIXED    
Severity: Normal    
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: All   
OS: All   
Attachments:
Description Flags
the patch oliver: review+

Description Filip Pizlo 2011-10-02 18:32:47 PDT
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.
Comment 1 Filip Pizlo 2011-10-02 18:35:05 PDT
Created attachment 109433 [details]
the patch
Comment 2 Filip Pizlo 2011-10-02 18:37:28 PDT
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
Comment 3 Filip Pizlo 2011-10-02 19:12:32 PDT
Landed in r96482.