125430 2013-12-08 14:35:02 -0800 CSE should work in SSA 2013-12-10 09:54:45 -0800 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) All All RESOLVED FIXED P2 Normal --- 112840 125429 1 fpizlo fpizlo barraclough ggaren mark.lam mhahnenberg msaboff nrotem oliver sam oldest_to_newest 957718 0 fpizlo 2013-12-08 14:35:02 -0800 Patch forthcoming. 957719 1 fpizlo 2013-12-08 14:35:12 -0800 This is actually non-trivial. 957724 2 218717 fpizlo 2013-12-08 15:37:44 -0800 Created attachment 218717 the patch 957736 3 nrotem 2013-12-08 19:00:39 -0800 >> m_graph.getBlocksInDepthFirstOrder(depthFirst); Why are you scanning the code in DFS? Is this a preparation for the multi-block CSE support? If it is then I have some code for that. Also, I think that I need some help with my CSE patch. It boosts one of the sun spider benchmarks by 30%, but I had a crash I could not debug when I was refactoring the code to use the DoesReadOrWrite API. 957737 4 fpizlo 2013-12-08 19:06:31 -0800 (In reply to comment #3) > >> m_graph.getBlocksInDepthFirstOrder(depthFirst); > > Why are you scanning the code in DFS? It guarantees that if A dominates B then I visit A before B. Essentially, CSE is doing a RAUW even though DFG doesn't have pointers from a node to its users. So even though I don't find global redundancies, I may have a basic block with: x: ValueAdd(@a, @b) y: ValueAdd(@a, @b) And @y gets used in some basic blocks dominated by this block. CSE is responsible for finding all of the uses of @y and replacing them with @x. That's why we do DFS order. > Is this a preparation for the multi-block CSE support? If it is then I have some code for that. Also, I think that I need some help with my CSE patch. It boosts one of the sun spider benchmarks by 30%, but I had a crash I could not debug when I was refactoring the code to use the DoesReadOrWrite API. OK - we should chat this week! 957748 5 nrotem 2013-12-08 20:18:51 -0800 (In reply to comment #4) > (In reply to comment #3) > > >> m_graph.getBlocksInDepthFirstOrder(depthFirst); > > > > Why are you scanning the code in DFS? > > It guarantees that if A dominates B then I visit A before B. Essentially, CSE is doing a RAUW even though DFG doesn't have pointers from a node to its users. So even though I don't find global redundancies, I may have a basic block with: > > x: ValueAdd(@a, @b) > y: ValueAdd(@a, @b) > > And @y gets used in some basic blocks dominated by this block. CSE is responsible for finding all of the uses of @y and replacing them with @x. That's why we do DFS order. > I know how dominator based value numbering works :) I was wondering why you are implementing it this way. My understanding is that this patch will not change anything since the code still does intra block cse. You will still need to support the non SSA dfg phase with the same code base, so I am not sure how you want to implement the multi block cse. The block scan order is the least of my worries. > > Is this a preparation for the multi-block CSE support? If it is then I have some code for that. Also, I think that I need some help with my CSE patch. It boosts one of the sun spider benchmarks by 30%, but I had a crash I could not debug when I was refactoring the code to use the DoesReadOrWrite API. > > OK - we should chat this week! 957750 6 fpizlo 2013-12-08 20:38:13 -0800 (In reply to comment #5) > (In reply to comment #4) > > (In reply to comment #3) > > > >> m_graph.getBlocksInDepthFirstOrder(depthFirst); > > > > > > Why are you scanning the code in DFS? > > > > It guarantees that if A dominates B then I visit A before B. Essentially, CSE is doing a RAUW even though DFG doesn't have pointers from a node to its users. So even though I don't find global redundancies, I may have a basic block with: > > > > x: ValueAdd(@a, @b) > > y: ValueAdd(@a, @b) > > > > And @y gets used in some basic blocks dominated by this block. CSE is responsible for finding all of the uses of @y and replacing them with @x. That's why we do DFS order. > > > > I know how dominator based value numbering works :) I was wondering why you are implementing it this way. That's the thing - this isn't meant to be dominator-based value numbering. This is still doing block-local CSE. The only thing global about it is propagating node->misc.replacement, which is like a bulk version of RAUW. I think we're in violent agreement over the fact that this isn't dominator based value numbering. It's not meant to be. This patch is just a bugfix to make it legal to run the current CSE phase in SSA mode. Previously doing so would either assert or corrupt the IR. > My understanding is that this patch will not change anything since the code still does intra block cse. Correct, for now. This work: https://bugs.webkit.org/show_bug.cgi?id=125253 will eventually benefit from it, since it's doing a lowering that happens after SSAification. The long-term idea is to do some DFG->DFG lowerings only along the FTL path. Then it makes sense to do some extra CSE along the FTL path, as well. > You will still need to support the non SSA dfg phase with the same code base, so I am not sure how you want to implement the multi block cse. The block scan order is the least of my worries. I'm not implementing multi-block CSE. This patch isn't intended to make multi-block CSE easier to implement. I'm just making it so that it is possible to run the existing CSE phase when in SSA form. Prior to this patch, if you needed to do *any* CSE - even the stupid block-local one - over SSA, you'd crash because the block-local CSE would either assert or corrupt the IR. I think that this patch is mainly interesting from the standpoint of just making all tests pass when CSE is run over SSA. Ultimately, I want all optimization phases to be runnable in SSA and to have some way of testing that they do, so that we have the option of doing SSAification prior to the optimization fixpoint in FTL mode. I suspect that if nothing else, this ought to reduce compile times. But it should also make the CFA and the folder more precise. On the topic of multi-block CSE, I'm not sure how much the DFG CSE is going to end up buying us, in FTL mode. It certainly finds *some* things that LLVM's GVN won't find (in case of nodes that call C functions that do write some memory but don't clobber the node being eliminated), but for *most* things, LLVM GVN+TBAA is likely to be strictly better. Maybe then the DFG CSE would serve a similar purpose to LLVM's EarlyCSE, which as I understand it, has more to do with compile times than anything else? > > > > Is this a preparation for the multi-block CSE support? If it is then I have some code for that. Also, I think that I need some help with my CSE patch. It boosts one of the sun spider benchmarks by 30%, but I had a crash I could not debug when I was refactoring the code to use the DoesReadOrWrite API. > > > > OK - we should chat this week! 958399 7 fpizlo 2013-12-10 09:54:45 -0800 Landed in http://trac.webkit.org/changeset/160328 218717 2013-12-08 15:37:44 -0800 2013-12-09 08:58:40 -0800 the patch blah.patch text/plain 3276 fpizlo SW5kZXg6IFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9DaGFuZ2VMb2cKPT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291 cmNlL0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkocmV2aXNpb24gMTYwMjkzKQorKysgU291cmNl L0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDE2IEBA CisyMDEzLTEyLTA4ICBGaWxpcCBQaXpsbyAgPGZwaXpsb0BhcHBsZS5jb20+CisKKyAgICAgICAg Q1NFIHNob3VsZCB3b3JrIGluIFNTQQorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9z aG93X2J1Zy5jZ2k/aWQ9MTI1NDMwCisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BT ISkuCisKKyAgICAgICAgKiBkZmcvREZHQ1NFUGhhc2UuY3BwOgorICAgICAgICAoSlNDOjpERkc6 OkNTRVBoYXNlOjpydW4pOgorICAgICAgICAoSlNDOjpERkc6OkNTRVBoYXNlOjpwZXJmb3JtTm9k ZUNTRSk6CisgICAgICAgICogZGZnL0RGR1BsYW4uY3BwOgorICAgICAgICAoSlNDOjpERkc6OlBs YW46OmNvbXBpbGVJblRocmVhZEltcGwpOgorCiAyMDEzLTEyLTA3ICBGaWxpcCBQaXpsbyAgPGZw aXpsb0BhcHBsZS5jb20+CiAKICAgICAgICAgRm9sZCB0eXBlZEFycmF5Lmxlbmd0aCBpZiB0eXBl ZEFycmF5IGlzIGNvbnN0YW50CkluZGV4OiBTb3VyY2UvSmF2YVNjcmlwdENvcmUvZGZnL0RGR0NT RVBoYXNlLmNwcAo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvSmF2YVNjcmlwdENvcmUvZGZnL0RGR0NT RVBoYXNlLmNwcAkocmV2aXNpb24gMTYwMjkzKQorKysgU291cmNlL0phdmFTY3JpcHRDb3JlL2Rm Zy9ERkdDU0VQaGFzZS5jcHAJKHdvcmtpbmcgY29weSkKQEAgLTQ4LDE1ICs0OCwyMSBAQCBwdWJs aWM6CiAgICAgCiAgICAgYm9vbCBydW4oKQogICAgIHsKLSAgICAgICAgQVNTRVJUKChjc2VNb2Rl ID09IE5vcm1hbENTRSkgPT0gKG1fZ3JhcGgubV9maXhwb2ludFN0YXRlID09IEZpeHBvaW50Tm90 Q29udmVyZ2VkKSk7CiAgICAgICAgIEFTU0VSVChtX2dyYXBoLm1fZml4cG9pbnRTdGF0ZSAhPSBC ZWZvcmVGaXhwb2ludCk7CiAgICAgICAgIAogICAgICAgICBtX2NoYW5nZWQgPSBmYWxzZTsKICAg ICAgICAgCiAgICAgICAgIG1fZ3JhcGguY2xlYXJSZXBsYWNlbWVudHMoKTsKICAgICAgICAgCi0g ICAgICAgIGZvciAodW5zaWduZWQgYmxvY2tJbmRleCA9IDA7IGJsb2NrSW5kZXggPCBtX2dyYXBo Lm51bUJsb2NrcygpOyArK2Jsb2NrSW5kZXgpCi0gICAgICAgICAgICBwZXJmb3JtQmxvY2tDU0Uo bV9ncmFwaC5ibG9jayhibG9ja0luZGV4KSk7CisgICAgICAgIGlmIChtX2dyYXBoLm1fZm9ybSA9 PSBTU0EpIHsKKyAgICAgICAgICAgIFZlY3RvcjxCYXNpY0Jsb2NrKj4gZGVwdGhGaXJzdDsKKyAg ICAgICAgICAgIG1fZ3JhcGguZ2V0QmxvY2tzSW5EZXB0aEZpcnN0T3JkZXIoZGVwdGhGaXJzdCk7 CisgICAgICAgICAgICBmb3IgKHVuc2lnbmVkIGkgPSAwOyBpIDwgZGVwdGhGaXJzdC5zaXplKCk7 ICsraSkKKyAgICAgICAgICAgICAgICBwZXJmb3JtQmxvY2tDU0UoZGVwdGhGaXJzdFtpXSk7Cisg ICAgICAgIH0gZWxzZSB7CisgICAgICAgICAgICBmb3IgKHVuc2lnbmVkIGJsb2NrSW5kZXggPSAw OyBibG9ja0luZGV4IDwgbV9ncmFwaC5udW1CbG9ja3MoKTsgKytibG9ja0luZGV4KQorICAgICAg ICAgICAgICAgIHBlcmZvcm1CbG9ja0NTRShtX2dyYXBoLmJsb2NrKGJsb2NrSW5kZXgpKTsKKyAg ICAgICAgfQogICAgICAgICAKICAgICAgICAgcmV0dXJuIG1fY2hhbmdlZDsKICAgICB9CkBAIC0x MDAwLDggKzEwMDYsMTAgQEAgcHJpdmF0ZToKICAgICAgICAgaWYgKGNzZU1vZGUgPT0gTm9ybWFs Q1NFKQogICAgICAgICAgICAgbV9ncmFwaC5wZXJmb3JtU3Vic3RpdHV0aW9uKG5vZGUpOwogICAg ICAgICAKLSAgICAgICAgaWYgKG5vZGUtPm9wKCkgPT0gU2V0TG9jYWwpCisgICAgICAgIGlmIChu b2RlLT5jb250YWluc01vdkhpbnQoKSkgeworICAgICAgICAgICAgQVNTRVJUKG5vZGUtPm9wKCkg IT0gWm9tYmllSGludCk7CiAgICAgICAgICAgICBub2RlLT5jaGlsZDEoKS0+bWVyZ2VGbGFncyhO b2RlUmVsZXZhbnRUb09TUik7CisgICAgICAgIH0KICAgICAgICAgCiAgICAgICAgIHN3aXRjaCAo bm9kZS0+b3AoKSkgewogICAgICAgICAKQEAgLTExMDUsNiArMTExMywxMSBAQCBwcml2YXRlOgog ICAgICAgICB9CiAgICAgICAgICAgICAKICAgICAgICAgY2FzZSBGbHVzaDogeworICAgICAgICAg ICAgaWYgKG1fZ3JhcGgubV9mb3JtID09IFNTQSkgeworICAgICAgICAgICAgICAgIC8vIEZJWE1F OiBFbmFibGUgRmx1c2ggc3RvcmUgZWxpbWluYXRpb24gaW4gU1NBIGZvcm0uCisgICAgICAgICAg ICAgICAgLy8gaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEyNTQyOQor ICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgfQogICAgICAgICAgICAgVmFyaWFi bGVBY2Nlc3NEYXRhKiB2YXJpYWJsZUFjY2Vzc0RhdGEgPSBub2RlLT52YXJpYWJsZUFjY2Vzc0Rh dGEoKTsKICAgICAgICAgICAgIFZpcnR1YWxSZWdpc3RlciBsb2NhbCA9IHZhcmlhYmxlQWNjZXNz RGF0YS0+bG9jYWwoKTsKICAgICAgICAgICAgIE5vZGUqIHJlcGxhY2VtZW50ID0gbm9kZS0+Y2hp bGQxKCkubm9kZSgpOwpJbmRleDogU291cmNlL0phdmFTY3JpcHRDb3JlL2RmZy9ERkdQbGFuLmNw cAo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09Ci0tLSBTb3VyY2UvSmF2YVNjcmlwdENvcmUvZGZnL0RGR1BsYW4uY3BwCShy ZXZpc2lvbiAxNjAyOTMpCisrKyBTb3VyY2UvSmF2YVNjcmlwdENvcmUvZGZnL0RGR1BsYW4uY3Bw CSh3b3JraW5nIGNvcHkpCkBAIC0yNjksNiArMjY5LDcgQEAgUGxhbjo6Q29tcGlsYXRpb25QYXRo IFBsYW46OmNvbXBpbGVJblRocgogICAgICAgICBwZXJmb3JtTGl2ZW5lc3NBbmFseXNpcyhkZmcp OwogICAgICAgICBwZXJmb3JtQ0ZBKGRmZyk7CiAgICAgICAgIHBlcmZvcm1MSUNNKGRmZyk7Cisg ICAgICAgIHBlcmZvcm1DU0UoZGZnKTsKICAgICAgICAgcGVyZm9ybUxpdmVuZXNzQW5hbHlzaXMo ZGZnKTsKICAgICAgICAgcGVyZm9ybUNGQShkZmcpOwogICAgICAgICBpZiAoT3B0aW9uczo6dmFs aWRhdGVGVExPU1JFeGl0TGl2ZW5lc3MoKSkK