RESOLVED FIXED 108868
DFG should have a precise view of jump targets
https://bugs.webkit.org/show_bug.cgi?id=108868
Summary DFG should have a precise view of jump targets
Filip Pizlo
Reported 2013-02-04 15:17:09 PST
This will reduce the pressure on the CFG simplifier.
Attachments
the patch (18.56 KB, patch)
2013-02-04 15:24 PST, Filip Pizlo
oliver: review+
patch for landing (17.01 KB, patch)
2013-02-04 19:30 PST, Filip Pizlo
no flags
Filip Pizlo
Comment 1 2013-02-04 15:24:28 PST
Created attachment 186476 [details] the patch
Oliver Hunt
Comment 2 2013-02-04 15:27:28 PST
Comment on attachment 186476 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=186476&action=review Looks fine, my only concern is whether std::sort is guaranteed to not be a stupid quick sort > Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp:116 > + std::sort(out.begin(), out.end()); How well does std::sort work on mostly ordered data?
Filip Pizlo
Comment 3 2013-02-04 15:30:42 PST
(In reply to comment #2) > (From update of attachment 186476 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=186476&action=review > > Looks fine, my only concern is whether std::sort is guaranteed to not be a stupid quick sort > > > Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp:116 > > + std::sort(out.begin(), out.end()); > > How well does std::sort work on mostly ordered data? I don't think I have a guarantee there. My recollection is that they don't do the rookie use-first-element-as-pivot mistake but I haven't read the code. But the performance numbers are looking consistently good... As well, even if std::sort were to deteriorate to O(n^2), it's O(n^2) over basic blocks and not instructions. The downside of _not_ running the precise jump target calculator is that we deteriorate to O(n^2) over instructions in the CFG simplifier - so much much worse. It would be great to try to optimize this code more, though, if we see it showing up as a hot spot.
Filip Pizlo
Comment 4 2013-02-04 15:31:06 PST
Oops, I'll have to do a pretty big rebase apparently.
Filip Pizlo
Comment 5 2013-02-04 19:30:09 PST
Created attachment 186526 [details] patch for landing
Filip Pizlo
Comment 6 2013-02-05 14:16:23 PST
Note You need to log in before you can comment on or make changes to this bug.