|Summary:||Constant folding in parser|
|Product:||WebKit||Reporter:||Gabor Loki <loki>|
|Severity:||Enhancement||CC:||darin, ggaren, mjs, oliver, zwarich|
|Version:||528+ (Nightly build)|
Description Gabor Loki 2008-06-06 08:35:56 PDT
Comment 1 Gabor Loki 2008-06-06 08:38:22 PDT
Created attachment 21527 [details] Const.Folding.v1 The patch is against rev 34372.
Comment 2 Gabor Loki 2008-06-09 01:13:01 PDT
Comment on attachment 21527 [details] Const.Folding.v1 I forgot to mark the patch with '?'. Note: This patch is not prepared to apply to trunk. I only ask for feedback.
Comment 3 Darin Adler 2008-06-09 06:48:22 PDT
Comment 4 Gabor Loki 2008-06-12 03:46:49 PDT
Comment 5 Darin Adler 2008-06-12 07:21:41 PDT
Comment 6 Maciej Stachowiak 2008-06-15 00:05:45 PDT
Some comments: 1) Instead of introducing new OP_WHATEVER enums for some of the operations, why not just use the existing op_ constants from the bytecode? 2) Is it really helpful to have a single foldConstant function which takes an opcode enum and then switches on it? Why not just a function for each type of fold? 3) Constant folds should be doable even if operand types aren't exactly what is expected, boolean string and number constants should be safely convertible. 4) We've discussed the possibility of doing constant folding at codegen time. I know it is a traditional parse-time optimization, but it fits very naturally with the way we want to have specialized versions of the opcodes with constant operands. If you have to handle the register-register, register-constant and constant-register cases, it makes sense to handle the constant-constant case right there. It has to be checked for anyway, because the parse-time constant folding here won't handle strings or various edge cases and folding seems like it is probably better than emitting excessive constant loads.
Comment 7 Maciej Stachowiak 2008-06-15 00:07:33 PDT
I'm not sure consideration #4 means that we shouldn't do parse-time constant folding for now, but it is something worth discussing.
Comment 8 Gabor Loki 2008-06-17 01:24:16 PDT
> 1) Instead of introducing new OP_WHATEVER enums for some of the operations, why > not just use the existing op_ constants from the bytecode? OpcodeID enum has so many enumerators. If I use those GCC will generate a bigger and less effective code for switch statement. The GCC generated tablejumps are very effective construction if the cases in a switch check for continuous (or almost continuous) numbers (like: 0,1,2,...,n). > 2) Is it really helpful to have a single foldConstant function which takes an > opcode enum and then switches on it? Why not just a function for each type of > fold? I am not sure which variant is better. With functions for each type of fold the tablejump can be saved. I will check it. > 3) Constant folds should be doable even if operand types aren't exactly what is > expected, boolean string and number constants should be safely convertible. What did I miss? > 4) We've discussed the possibility of doing constant folding at codegen time. You are right about not every constant can be handled quick in parse-time, but IMHO this should not be the only priority. If the AST is smaller the codegen will be also quicker. In addition if you like have a lightweight constant propagation, it is better to have constant folding in AST instead of in codegen. time. Of course, codegen. can have its own separate constant folding.
Comment 9 Gabor Loki 2008-07-16 03:49:12 PDT
Comment 10 Gabor Loki 2008-07-16 03:57:43 PDT
Created attachment 22303 [details] Fold only *, +, <<, >>, ~ operators (v2) Opps, I forgot to remove an unnecessary include header from the patch. Sorry.
Comment 11 Oliver Hunt 2008-07-20 14:05:45 PDT
Comment on attachment 22303 [details] Fold only *, +, <<, >>, ~ operators (v2) This basically looks good. Unfortunately iev made some parser changes which *may* conflict with your changes (not in any real way though). If you could bring your patch up to ToT and include commandline performance numbers that would be awesome
Comment 12 Gabor Loki 2008-07-22 02:02:25 PDT
Created attachment 22422 [details] Fold only *, +, <<, >>, ~ operators (v3) Here is the requested patch (rev. 35284). The SunSpider result: ** TOTAL **: - 2817.0ms +/- 0.9% 2816.7ms +/- 0.7% Measured on qt-linux with the patch of https://bugs.webkit.org/show_bug.cgi?id=20097 bug.
Comment 13 Cameron Zwarich (cpst) 2008-07-22 02:10:12 PDT
Do you know where this actually gets triggered in SunSpider?
Comment 14 Gabor Loki 2008-07-22 03:37:57 PDT
The patch does constant folding on the following JS lines. '*' : - 3d-cube.js:311 - 3d-raytrace.js:316 '<<' : - crypto-aes.js:369 '+' : - crypto-md5:175 - crypto-sha1:121
Comment 15 Geoffrey Garen 2008-07-29 17:33:17 PDT
If you added division to the pass, you would also catch this important line from math-partial-sums.js: var twothirds = 2.0/3.0;
Comment 16 Cameron Zwarich (cpst) 2008-08-01 16:23:24 PDT
Comment 17 Gabor Loki 2008-08-26 03:36:04 PDT
Comment 18 Cameron Zwarich (cpst) 2008-08-28 13:26:31 PDT
I will review this soon.
Comment 19 Cameron Zwarich (cpst) 2008-08-28 21:24:34 PDT
Created attachment 23063 [details] SunSpider results for last patch against r35965 Your SunSpider results had a very wide variance, so I ran SunSpider myself. There is no noticeable change on SunSpider, which is what I suspect, but I still think that this patch can be landed. It was a slight regression on Oliver's machine, but that might be entirely random. If it is a problem later, we can always back it out.
Comment 20 Cameron Zwarich (cpst) 2008-08-28 21:51:02 PDT
Comment on attachment 22997 [details] Fold only *, +, <<, >>, ~ operators (v4) I think it would be best to make m1 and m2 more descriptive, like expr1 and expr2. You don't want them too long, because some of this code is already quite lengthy, but those would be better than m1 and m2. Also, locHasAssignments doesn't really make the most sense here. In makeAssignNode(), locHasAssignments refers to the location of the assignment. For these binary operations, it should be rightHasAssignments, because we are concerned about the right expression having assignments. I can make both of these changes when I land the patch, if you'd like. I still find the shouldBeRound() thing sort of odd, because the value it prints is not actually the result of the operation. You could have used different values that would work out exactly. However, I won't complain too much. More tests are always welcome, and I can always change it if I want.
Comment 21 Gabor Loki 2008-08-29 00:04:10 PDT
(In reply to comment #20) > I can make both of these changes when I land the patch, if you'd like. I agree with you about renaming. If you could do both changes during landing I would appreciate that. > I still find the shouldBeRound() thing sort of odd, because the value it prints > is not actually the result of the operation. You could have used different > values that would work out exactly. I will look into it again, read what ecma says about rounding, and try to check it on other platform.
Comment 22 Cameron Zwarich (cpst) 2008-08-31 11:47:13 PDT
(In reply to comment #21) > I will look into it again, read what ecma says about rounding, and try to check > it on other platform. ECMA states that all arithmetic is done with double precision IEEE floating-point, and the result of the calculation you use in your tests can not be represented exactly. You could just write the full value of the result in the tests or pick different calculations whose can be represented exactly. I'll even do it while landing, if you want. For now, I'll r- the patch so no one lands it.
Comment 23 Cameron Zwarich (cpst) 2008-08-31 11:47:52 PDT
Comment on attachment 22997 [details] Fold only *, +, <<, >>, ~ operators (v4) Clearing review flag while waiting for a response from Gabor.
Comment 24 Gabor Loki 2008-09-01 03:26:20 PDT
Created attachment 23095 [details] Fold *, /, +, <<, >>, ~ operators (v5) I have added the requested changes: - rename m1, m2 to expr1, expr2 - rename locHasAssignments to rightHasAssignments - remove shouldBeRound function and use double-precision values in the test cases
Comment 25 Cameron Zwarich (cpst) 2008-09-06 18:34:15 PDT
I'll review this tonight. I just want to get some new SunSpider numbers. We have been having some weird problems with frontend changes pissing off GCC.
Comment 26 Darin Adler 2008-09-21 11:40:40 PDT
Comment on attachment 23095 [details] Fold *, /, +, <<, >>, ~ operators (v5) + if (v2 != 0) + return makeNumberNode(globalPtr, v1 / v2); Why can't this be done for 0 too? Sure, it would make a NaN node, but is there a problem with that? Great test case, but I don't really find the test case easier to read with all that space padding in it. What effect does this have on performance? Maybe I'll test it.
Comment 27 Darin Adler 2008-09-21 12:15:29 PDT
Comment on attachment 23095 [details] Fold *, /, +, <<, >>, ~ operators (v5) r=me
Comment 28 Darin Adler 2008-09-21 12:19:48 PDT
Others say they can't measure consistent SunSpider results on this, but I do see a consistent speedup. It's in: http://trac.webkit.org/changeset/36739 The code in negate is strange -- I don't see any reason we have to modify the number node in place rather than making a new one, and I don't see any reason to skip the optimization for 0 and negative numbers. I'm going to close this as fixed.