Bug 151141

Created attachment 279663 [details] work in progress

(In reply to comment #0) > - Introduce a new B3 Opcode called AwesomeJump that takes a pointer to jump > to and a list of BasicBlocks that are possible successors. Is there any other name that can be more descriptive (but still concise) than AwesomeJump? The name AwesomeJump really doesn't say anything but "grep for me and hope to find a comment explaining what I am".

(In reply to comment #2) > (In reply to comment #0) > > - Introduce a new B3 Opcode called AwesomeJump that takes a pointer to jump > > to and a list of BasicBlocks that are possible successors. > > Is there any other name that can be more descriptive (but still concise) > than AwesomeJump? The name AwesomeJump really doesn't say anything but > "grep for me and hope to find a comment explaining what I am". The patch calls it LeapOfFaith. I think that the semantics are weird enough that it needs a weird name. Also, in B3, you don't need to grep - just visit webkit.org/docs/b3/intermediate-representation.html. The attached patch adds a definition of LeapOfFaith to that document. I considered other names, but rejected them, because they'd do more harm than good. LeapOfFaith has semantics that are hard to summarize in a descriptive name. If someone just reads the name of the opcode and then fails to read the details, they will surely end up making a mistake in their reasoning: - IndirectJump. This doesn't really capture the meaning of the opcode. LeapOfFaith transfers control to one of a specific set of basic blocks. Half of the opcode's meaning is that control will be transfered to one of those blocks, sort of like how a Switch would work. You can't use LeapOfFaith the way that you would ordinarily use IndirectJump. For example, you can't use it to implement tail calls. - TableSwitch. This doesn't really capture the meaning either, since LeapOfFaith doesn't require there to be a table. We could go with a super verbose name, like IndirectJumpToBlockInList, but I'm not sure that this actually describes what is going on either. For those reasons, I think that LeapOfFaith is a pretty good name because that's what I picture it doing. You use the opcode when you're super confident that you can arrange for the jump address to be the address of some basic block in the successor list, and the compiler has no choice but to trust you. The compiler is taking a leap of faith.

I discovered an interesting problem with this. This means that after switch lowering, we can't duplicate or specialize code anymore. That might be a problem.

(In reply to comment #4) > I discovered an interesting problem with this. This means that after switch > lowering, we can't duplicate or specialize code anymore. That might be a > problem. It's actually not that bad. Callbacks have well-defined semantics. If a basic block has callbacks then we know that someone is interested in the block's address. We can duplicate the block, so long as we still have some block that represents whatever it meant to jump to the original block. That meaning can be described by the predecessors of the block that used LeapOfFaith. This is very confusing. I will have to think about it a bit more before concluding that this patch is a good idea.

This makes big switch statements (~60 cases) about 30% faster. I think this means that we need to be willing to accept some compiler grossness to support this feature.

Created attachment 279705 [details] close to done

Created attachment 279733 [details] performance

Created attachment 279734 [details] it works, sort of, but it's the wrong approach

Attachment 279734 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3BlockInsertionSet.cpp:105: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:338: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:354: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:358: One line control clauses should not use braces. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirBasicBlock.cpp:75: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3BasicBlock.cpp:126: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:191: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:193: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10134: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/B3LowerToAir.cpp:92: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 10 in 28 files If any of these errors are false positives, please file a bug against check-webkit-style.

Comment on attachment 279734 [details] it works, sort of, but it's the wrong approach Actually, I thought about this more, and realized a big error. In this approach, LeapOfFaith can only branch to blocks that have callbacks. That's something we can validate. But it's actually more than this; LeapOfFaith must continue to always branch to the same blocks that it had when it was created, modulo some clear cases where it can be repointed and fixed up (like if you create a new block that is a stand-in for an old one - then you just transfer the callbacks to then new one). But this is impossible to guarantee. Consider that we may have two LeapOfFaiths that both have the same block as a successor. This means we will have two critical edges, which we may break at any time. A fundamental law of B3 is that critical edges are breakable and any phase may do this. But there is no way to transfer callbacks in this case. The original successor block would have had two callbacks - one for each LeapOfFaith. But these callbacks do not identify themselves as corresponding to any particular LeapOfFaith. So, critical edge breaking has no way to know which newly created block should get which callback. We could maybe label callbacks according to which LeapOfFaith they correspond to, but this seems like it would just make all of B3 much more complex. Luckily, there's a solution, and it would result in a significantly smaller patch: make LeapOfFaith have the callback. This way, each LeapOfFaith will report, at the bitter end of compilation, the branch destinations for each of its successors. Under this approach, we would only need one additional law to keep things sane: LeapOfFaith cannot be cloned. I believe that this would be OK. In the past we have assumed that all code can be cloned. That's basically the only cost of this kind of LeapOfFaith. I think that if we do this, we should also extend the "no-clone" rule to other things - for example, Patchpoints should be able to flag themselves as no-clone in those cases where the client is not equipped to deal with one patchpoint being emitted multiple times.

Somewhat humorously, my new approach would make it nearly impossible to implement threaded interpreters in B3. I think that's actually OK. The GCC-style address-of-label approach is pretty dirty. I didn't realize just how dirty it was until I started thinking about blocks with callbacks. If we ever did want B3 to support threaded interpreters, then I think we'd do it by increasing B3's snippet compilation chops. Imagine if you could tell a bunch of B3::Procedures that they should agree on the same stack layout and pin the same registers for some common state. Then you could express each opcode as its own Procedure. This would obviate the need to teach the compiler how to reason about control flow between opcodes in the interpreter.

Just throwing some ideas out for alternate names to "LeapOfFaith". What do you think of "MultipleTargetJump" or "NTargetJump"? While we can explain why "LeapOfFaith" can fit, it still sounds like a bit of a stretch. And anyone new to the code will have a hard time extrapolating from "LeapOfFaith" to what it does. Just my $.02.

(In reply to comment #13) > Just throwing some ideas out for alternate names to "LeapOfFaith". What do > you think of "MultipleTargetJump" or "NTargetJump"? I don't think that MultipleTargetJump is an accurate name for this opcode. Any branching instruction with multiple targets can be describes as a multiple target jump. The special thing about LeapOfFaith is that we're asking the compiler to trust that the arbitrary pointer value being passed as an operand ends up being the address of one of the basic blocks listed as successors. > > While we can explain why "LeapOfFaith" can fit, it still sounds like a bit > of a stretch. And anyone new to the code will have a hard time > extrapolating from "LeapOfFaith" to what it does. Just my $.02.

Created attachment 279896 [details] a better approach I haven't tried compiling this yet. I'm saving it here while I move on to more important things.

(In reply to comment #13) > Just throwing some ideas out for alternate names to "LeapOfFaith". What do > you think of "MultipleTargetJump" or "NTargetJump"? > > While we can explain why "LeapOfFaith" can fit, it still sounds like a bit > of a stretch. And anyone new to the code will have a hard time > extrapolating from "LeapOfFaith" to what it does. Just my $.02. I think this argument cuts to the heart of where we disagree. I *want* people to have a hard time extrapolating from the name "LeapOfFaith" what it does. I want them to say "gosh, that's weird" and read the docs. This is because its behavior is so bizarre when compared to traditional compiler constructs. Putting "Jump" into the title and prefixing it with something that implies that it might jump to multiple places or that the jump target is unknown would cause more confusion than the current name. The worst case scenario is that a compiler hacker reads the name and assumes, based on the name alone, that it's just like an indirect jump (jumps anywhere without bound) or that it's like a switch (it's just another control construct with no sneakiness). This would be wrong because: - Unlike an indirect jump, we have a bound on the set of targets. - Unlike a switch, it takes a raw pointer as an operand and it executes by doing an unchecked indirect jump to that pointer. - Unlike either a switch or an indirect jump, it carries identity. I.e. it is not cloneable. - Unlike a switch or indirect jump, it requires a callback to the client in order to have meaning. So, if the name "LeapOfFaith" causes enough confusion to force the user to read what it does, then the name has accomplished its mission. This is sort of like other names in B3, like ChillDiv and Upsilon. We intentionally avoid using terms of art for these because there is no term of art that accurately corresponds to what those opcodes do, so we want people to read up on this. It's also in keeping with compiler tradition. For example, when SSA was invented, it came with the "Phi" operation. Why "Phi"? Because there's no concise name that accurately describes a Phi's behavior. Using a weirdo name ensures confusion, which then increases the chances that anyone unfamiliar will RTFM. ;-)

Created attachment 279961 [details] I don't even know if it compiles

Created attachment 279962 [details] it's getting so bizarre

Created attachment 279996 [details] a bit more

(In reply to comment #14) > (In reply to comment #13) > > Just throwing some ideas out for alternate names to "LeapOfFaith". What do > > you think of "MultipleTargetJump" or "NTargetJump"? > > I don't think that MultipleTargetJump is an accurate name for this opcode. > Any branching instruction with multiple targets can be describes as a > multiple target jump. The special thing about LeapOfFaith is that we're > asking the compiler to trust that the arbitrary pointer value being passed > as an operand ends up being the address of one of the basic blocks listed as > successors. > > > > > While we can explain why "LeapOfFaith" can fit, it still sounds like a bit > > of a stretch. And anyone new to the code will have a hard time > > extrapolating from "LeapOfFaith" to what it does. Just my $.02. Mark and Ben both objected to the name "LeapOfFaith". I concede, it's a weird name. I've renamed it to PolyJump. I think it's a good name: - It has "Jump" in the name. So, you know that its job is to take you from this basic block to another basic block. - This matches our existing MacroAssembler's naming convention for indirect branches, which call it a "jump", based on x86 naming conventions. - This matches our existing use of the word "Poly" (short for "polymorphic") to mean that we're doing a dispatch that can take us to one of many places. - It's concise. I rejected "MultiJump" because we're not actually emitting multiple things. I believe that either "poly" or "virtual" are the best names to use in cases where there is one operation that may have polymorphic (aka virtual) behavior. I picked "Poly" over "Virtual" just because it's shorter, but other than this, I like "Virtual" as much as I like "Poly".

Created attachment 280062 [details] the patch It works!!!

Attachment 280062 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3PolyJumpValue.h:46: The parameter name "task" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:262: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:38: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10142: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12119: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12281: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 7 in 35 files If any of these errors are false positives, please file a bug against check-webkit-style.

Comment on attachment 280062 [details] the patch Attachment 280062 [details] did not pass mac-debug-ews (mac): Output: http://webkit-queues.webkit.org/results/1403224 New failing tests: js/regress/switch-string-big-length-tower-var.html js/regress/switch.html js/regress/switch-string-basic-big-var.html js/regress/switch-constant.html js/regress/bigswitch.html js/regress/switch-string-basic-var.html

Created attachment 280063 [details] Archive of layout-test-results from ews113 for mac-yosemite The attached test failures were seen while running run-webkit-tests on the mac-debug-ews. Bot: ews113 Port: mac-yosemite Platform: Mac OS X 10.10.5

Comment on attachment 280062 [details] the patch Investigating debug issues.

(In reply to comment #25) > Comment on attachment 280062 [details] > the patch > > Investigating debug issues. Ha, it's probably this silly assertion: ASSERT(block->successors().size() <= 2);

Created attachment 280064 [details] the patch Fixed the debug failures by removing a bogus assertion.

Attachment 280064 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3PolyJumpValue.h:46: The parameter name "task" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:262: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:38: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10142: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12119: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12281: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 7 in 35 files If any of these errors are false positives, please file a bug against check-webkit-style.

Comment on attachment 280064 [details] the patch Attachment 280064 [details] did not pass mac-ews (mac): Output: http://webkit-queues.webkit.org/results/1404435 Number of test failures exceeded the failure limit.

Created attachment 280068 [details] Archive of layout-test-results from ews102 for mac-yosemite The attached test failures were seen while running run-webkit-tests on the mac-ews. Bot: ews102 Port: mac-yosemite Platform: Mac OS X 10.10.5

Created attachment 280103 [details] the patch

Attachment 280103 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3PolyJumpValue.h:46: The parameter name "task" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:262: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:38: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10142: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12119: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12281: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 7 in 35 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 280834 [details] the patch Rebased patch

Attachment 280834 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3PolyJumpValue.h:46: The parameter name "task" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:275: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:38: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10142: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12119: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12281: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 7 in 35 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 281153 [details] the patch rebased

Attachment 281153 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3PolyJumpValue.h:46: The parameter name "task" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:275: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:38: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10142: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12119: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12281: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 7 in 35 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 281475 [details] the patch Rebased again.

Attachment 281475 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3PolyJumpValue.h:46: The parameter name "task" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:275: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:38: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10142: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12119: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12281: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 7 in 35 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 282088 [details] the patch

Attachment 282088 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3PolyJumpValue.h:46: The parameter name "task" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:275: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:38: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10142: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12119: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12281: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 7 in 35 files If any of these errors are false positives, please file a bug against check-webkit-style.

I'm starting to think that the no-clone restriction of PolyJump is not very good. We want to be able to clone code. This just came up with EntrySwitch. Also, the reason why PolyJump is not cloneable is that it is preceded by code that materialized the pointer to the jump table and loads a jump target from it. Maybe it's better if that code is part of the PolyJump. That is, we replace PolyJump with CustomJump or something. It's a patchpoint in terminal position.

OK, to implement CustomJump we would need to either introduce multiple inheritance into the Value hierarchy (CustomJumpValue would be a subclass of ControlValue and StackmapValue) or we need to reintroduce B3::Stackmap, which is the part of StackmapValue that would get shared by StackmapValue and CustomJumpValue. We could also remove the requirement that the terminal is a ControlValue. That's tempting, since there's less data in a ControlValue and so it would be easier to sort of duplicate it. But, that would mean that every access to successors would be come polymorphic. That's probably not so good.

Actually, it would make the most sense to just refactor how we handle control values. ControlValue only exists because we opted not to put the successor list in BasicBlock. We should just do that. Then, PatchpointValue or one of its close relatives could be used as a control.

Which should we choose: - Have StackmapGenerationParams include a Vector<CCallHelpers::Label>. This would be awkward. We can't actually use Label because of forward edges. One option would be to include a Vector<Box<Label>> or Box<Vector<Label>>. Box<Vector<Label>> seems better. But imagine this: Air::generate() creates a Vector<Box<Label>> to hold the eventual labels of all basic blocks. Air::GenerationContext may even have a reference to this. Then, when generating code for a terminal patchpoint, we would create a Vector<Box<Label>> for those labels that correspond to the block's successors, by just copying them out of the Vector<Box<Label>> in the GenerationContext. - Have a second, link-time callback. It will be up to the client to sort out how to communicate between the compile-time callback and the link-time callback. This is awkward because of cloning. The client can't simply create one Box<> to carry the state, since we might compile two versions and then link two versions. The Box<> would contain the data of the second version, while the data for the first version will be lost. Note that it appears that if we just factor successors out of ControlValue - thereby killing the ControlValue class - then we have the most beautiful way of determining if something is terminal: value->effects().terminal. This means that Patchpoint will Just Work as a terminal if the client sets patchpoint->effects.terminal = true!

Created attachment 282728 [details] rebased patch Uploading rebased patch before I change the approach to make Patchpoint into a valid terminal.

Attachment 282728 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3PolyJumpValue.h:46: The parameter name "task" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:275: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:38: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10184: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12161: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12323: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 7 in 35 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 282730 [details] a new approach Starting to remove ControlValue

Created attachment 282731 [details] a bit more So much fun

Comment on attachment 282728 [details] rebased patch Looks like this patch wasn't properly rebased.

Created attachment 282732 [details] tiny bit more

Created attachment 282733 [details] so fun Wow, removing ControlValue lets me remove some nasty garbage, like the weirdo terminal validation in resetReachability().

Created attachment 282819 [details] a tiny bit more I think that now most of the IR does not care about ControlValue.

Created attachment 282823 [details] so small patch

Created attachment 282846 [details] maybe it's done I don't know if it's done or not, since I haven't even tried compiling it. But the basic idea is this: - Remove ControlValue. Now, the successors of a basic block are stored in a basic block. - Any B3 opcode or Value subclass can be a terminal. You know if it's terminal if you call Value::effects().terminal. Patchpoints may be terminal or not depending on PatchpointValue::effects. - Any Air opcode can be a terminal. You know if it's terminal if you call Inst::isTerminal(). Patches can be terminal or not depending on Special::isTerminal(Inst&). - StackmapGenerationParams can tell a terminal Patchpoint what the Box<Label> is for each successor. You know that the boxes will be filled by the time late paths execute. - LowerMacros uses a terminal Patchpoint to create a jump through a jump table. I still have a few clean-ups to do. The patch still refers to PolyJump. But it's basically done.

Created attachment 282847 [details] a bit more Removed all of the cloneable garbage. This new patch does not prevent cloning. I don't think we want to prevent cloning because of how we will do LowerEntrySwitch.

Created attachment 283054 [details] closer to done Fixed up the threaded interpreter test.

Created attachment 283059 [details] made some things compile

Created attachment 283067 [details] more compile fixes

Created attachment 283104 [details] it seems to work! Still need to run more tests, but so far it seems solid.

Created attachment 283113 [details] maybe done Seems to work!!

Attachment 283113 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3CaseCollectionInlines.h:32: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10182: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12155: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12161: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12325: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:366: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 7 in 55 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 283169 [details] the patch

Attachment 283169 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3CaseCollectionInlines.h:32: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10182: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12155: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12161: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12325: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:366: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 7 in 55 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 283207 [details] the patch

Attachment 283207 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3CaseCollectionInlines.h:32: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10182: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12155: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12161: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12325: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:366: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 7 in 55 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 283217 [details] the patch

Attachment 283217 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3CaseCollectionInlines.h:32: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10182: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12155: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12161: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12325: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:351: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:366: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 7 in 55 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 283288 [details] the patch

Attachment 283288 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3CaseCollectionInlines.h:32: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10182: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12160: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12170: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12320: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:355: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:372: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 7 in 56 files If any of these errors are false positives, please file a bug against check-webkit-style.

Comment on attachment 283288 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=283288&action=review Partial review. No real problem so far. I am gonna get Cécile at the airport, then I'll finish when I come back to IL. > Source/JavaScriptCore/ChangeLog:258 > + (JSC::B3::shouldBeVerbose): Let's drop all the functions names, that's huge and useless. > Source/JavaScriptCore/b3/B3BasicBlock.cpp:54 > + value->owner = this; Is that needed? So far we have only set the owners explicitly. > Source/JavaScriptCore/b3/B3BasicBlock.cpp:61 > + value->owner = this; ditto. > Source/JavaScriptCore/b3/B3BasicBlock.cpp:98 > +void BasicBlock::setSuccessors(const FrequentedBlock& target) setSuccessors(), not setSuccessor()? > Source/JavaScriptCore/b3/B3BasicBlock.cpp:157 > + if (successors().size()) { "!successors().isEmpty()" is the WebKit style. > Source/JavaScriptCore/b3/B3BasicBlock.cpp:162 > + out.print(listDump(successors())); This case freaks me out, successors without terminal? > Source/JavaScriptCore/b3/B3BasicBlock.h:82 > - > + Oops, not needed. > Source/JavaScriptCore/b3/B3BasicBlock.h:121 > + // This is only valid for Branch and Switch. Valid for Branch? Is that useful? > Source/JavaScriptCore/b3/B3BasicBlock.h:140 > - > + We remove spaces, not add them :) > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:75 > + if (block->size() > m_maxSize > + || block->numSuccessors() > m_maxSuccessors) This looked better on one line, no need to change it. > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:77 > - > + Oops. > Source/JavaScriptCore/b3/B3LowerMacros.cpp:302 > + if ((lastValue - firstValue + 1) / cases.size() < densityLimit) { Does validation prevent a Switch with only a fallback? Otherwise we could divide by zero here.

(In reply to comment #70) > Comment on attachment 283288 [details] > the patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=283288&action=review > > Partial review. No real problem so far. > I am gonna get Cécile at the airport, then I'll finish when I come back to > IL. Thanks! > > > Source/JavaScriptCore/ChangeLog:258 > > + (JSC::B3::shouldBeVerbose): > > Let's drop all the functions names, that's huge and useless. OK. > > > Source/JavaScriptCore/b3/B3BasicBlock.cpp:54 > > + value->owner = this; > > Is that needed? > So far we have only set the owners explicitly. It is now, but only for the benefit of the client (FTL or testb3). The client gets this guarantee: if they append a value to a block using one of these APIs or something that bottoms out in it (like block->appendNew<Type>(things)), then the newly created value will have the owner set to the block you added it to. This is useful for APIs like SwitchValue::appendCase(), which comes in two varieties: one where you pass the owner explicitly and another where you rely on Value::owner being set. This means that FTL can do: SwitchValue* switchValue = block->appendNew<SwitchValue>(...); switchValue->appendCase(case); // no need to pass block here because switchValue->owner == block > > > Source/JavaScriptCore/b3/B3BasicBlock.cpp:61 > > + value->owner = this; > > ditto. > > > Source/JavaScriptCore/b3/B3BasicBlock.cpp:98 > > +void BasicBlock::setSuccessors(const FrequentedBlock& target) > > setSuccessors(), not setSuccessor()? I don't care. I went back and forth on this. This is a setter for the successors array, so I went with setSuccessors(). I think it makes sense either way. > > > Source/JavaScriptCore/b3/B3BasicBlock.cpp:157 > > + if (successors().size()) { > > "!successors().isEmpty()" is the WebKit style. Fixed! > > > Source/JavaScriptCore/b3/B3BasicBlock.cpp:162 > > + out.print(listDump(successors())); > > This case freaks me out, successors without terminal? When we generate bad IR, we dump it to see why it's bad. For this reason, I want the dumping code to still dump things even when you make silly mistakes like create empty basic blocks or blocks without terminals. > > > Source/JavaScriptCore/b3/B3BasicBlock.h:82 > > - > > + > > Oops, not needed. Fixed. > > > Source/JavaScriptCore/b3/B3BasicBlock.h:121 > > + // This is only valid for Branch and Switch. > > Valid for Branch? Is that useful? We definitely use it for SwitchValue. I observed that "fall through" is also a thing that works for Branch for free: the last successor of a Branch is the notTaken, which is the same thing as a fallThrough. So, I relaxed the assert to allow it. > > > Source/JavaScriptCore/b3/B3BasicBlock.h:140 > > - > > + > > We remove spaces, not add them :) Fixed. > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:75 > > + if (block->size() > m_maxSize > > + || block->numSuccessors() > m_maxSuccessors) > > This looked better on one line, no need to change it. Fixed. > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:77 > > - > > + > > Oops. Fixed. > > > Source/JavaScriptCore/b3/B3LowerMacros.cpp:302 > > + if ((lastValue - firstValue + 1) / cases.size() < densityLimit) { > > Does validation prevent a Switch with only a fallback? > Otherwise we could divide by zero here. It's totally valid to have a Switch with only a fallback. This code will not divide by zero because it's guarded by a check above that there is some minimal number of cases: if (end - start >= minCasesForTable) {

Created attachment 283928 [details] the patch Addressed Ben's feedback

> > > > > Source/JavaScriptCore/b3/B3LowerMacros.cpp:302 > > > + if ((lastValue - firstValue + 1) / cases.size() < densityLimit) { > > > > Does validation prevent a Switch with only a fallback? > > Otherwise we could divide by zero here. > > It's totally valid to have a Switch with only a fallback. This code will > not divide by zero because it's guarded by a check above that there is some > minimal number of cases: > > if (end - start >= minCasesForTable) { Oh shit, and the logic here is subtly too conservative. Instead of: if ((lastValue - firstValue + 1) / cases.size() < densityLimit) { It should say: if ((lastValue - firstValue + 1) / (end - start) < densityLimit) { Because [start, end) is the part of 'cases' that we are working on right now.

Attachment 283928 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3CaseCollectionInlines.h:32: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10182: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12160: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12170: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12320: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:355: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:372: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 7 in 56 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 283935 [details] the patch Fixed the bug with LowerMacros using cases.size() where it meant end-begin.

Attachment 283935 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3CaseCollectionInlines.h:32: Alphabetical sorting problem. [build/include_order] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:10182: Missing spaces around / [whitespace/operators] [3] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12160: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12170: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:12320: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:355: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3LowerMacros.cpp:372: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 7 in 56 files If any of these errors are false positives, please file a bug against check-webkit-style.

Comment on attachment 283935 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=283935&action=review > Source/JavaScriptCore/b3/B3LowerMacros.cpp:302 > + // better than a binary switch. > + const unsigned minCasesForTable = 7; > + const unsigned densityLimit = 4; > + if (end - start >= minCasesForTable) { > + int64_t firstValue = cases[start].caseValue(); > + int64_t lastValue = cases[end - 1].caseValue(); > + if ((lastValue - firstValue + 1) / (end - start) < densityLimit) { Can we make this decision a helper function to reduce indentation? > Source/JavaScriptCore/b3/B3StackmapGenerationParams.h:95 > + > + // This is computed lazily, so it won't work if you capture StackmapGenerationParams by value. > + // These labels will get populated before any late paths or link tasks execute. > + JS_EXPORT_PRIVATE Vector<Box<CCallHelpers::Label>> successorLabels() const; > + > + // This is computed lazily, so it won't work if you capture StackmapGenerationParams by value. > + // Returns true if the successor at the given index is going to be emitted right after the > + // patchpoint. > + bool fallsThroughToSuccessor(unsigned successorIndex) const; I don't fully get this. I see that these values are computed on the fly, but I don't see why the computation would become wrong after copy construction.

Comment on attachment 283935 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=283935&action=review > Source/JavaScriptCore/b3/B3BasicBlock.h:123 > + // This is only valid for Branch and Switch. > + const FrequentedBlock& fallThrough() const; > + FrequentedBlock& fallThrough(); I understand your rationale for fallThrough() now but I believe stronger definition is better. I don't care a lot. It's fine to keep it if you like fallThrough(). > Source/JavaScriptCore/b3/B3LowerToAir.cpp:2443 > - > + Oops. > Source/JavaScriptCore/b3/B3Opcode.h:219 > - > + Oops > Source/JavaScriptCore/b3/B3Value.h:116 > + void replaceWithJump(BasicBlock* owner, const FrequentedBlock&); > + void replaceWithOops(BasicBlock* owner); We were more or less avoiding those before. There is even a comment: // Note that the opcode is immutable, except for replacing values with Identity or Nop. Opcode opcode() const { return m_opcode; } We should remove the comment since we have embraced mutation in a few places. > Source/JavaScriptCore/b3/B3Value.h:237 > - > + Oops > Source/JavaScriptCore/b3/air/AirGenerate.cpp:205 > + context.indexInBlock = UINT_MAX; numeric_limits<> is more WebKit-like. > Source/JavaScriptCore/b3/air/AirGenerate.cpp:243 > - > + Oops. > Source/JavaScriptCore/b3/air/AirGenerationContext.h:49 > + unsigned indexInBlock { UINT_MAX }; numeric_limits

(In reply to comment #77) > Comment on attachment 283935 [details] > the patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=283935&action=review > > > Source/JavaScriptCore/b3/B3LowerMacros.cpp:302 > > + // better than a binary switch. > > + const unsigned minCasesForTable = 7; > > + const unsigned densityLimit = 4; > > + if (end - start >= minCasesForTable) { > > + int64_t firstValue = cases[start].caseValue(); > > + int64_t lastValue = cases[end - 1].caseValue(); > > + if ((lastValue - firstValue + 1) / (end - start) < densityLimit) { > > Can we make this decision a helper function to reduce indentation? Either way, we need to capture firstValue and lastValue. So, to reduce indentation, we'd have to introduce some kind of possibly less intuitive way of getting those values. > > > Source/JavaScriptCore/b3/B3StackmapGenerationParams.h:95 > > + > > + // This is computed lazily, so it won't work if you capture StackmapGenerationParams by value. > > + // These labels will get populated before any late paths or link tasks execute. > > + JS_EXPORT_PRIVATE Vector<Box<CCallHelpers::Label>> successorLabels() const; > > + > > + // This is computed lazily, so it won't work if you capture StackmapGenerationParams by value. > > + // Returns true if the successor at the given index is going to be emitted right after the > > + // patchpoint. > > + bool fallsThroughToSuccessor(unsigned successorIndex) const; > > I don't fully get this. I see that these values are computed on the fly, but > I don't see why the computation would become wrong after copy construction. The implementation uses StackmapGenerationParams' reference to Air::GenerationContext, which mutates as we compile. So if you capture the StackmapGenerationParams (by value or any other way) inside a nested lambda inside your stackmap generator, then you're going to have a bad time. That nested lambda may run when the GenerationContext is no longer in the state you wanted. In particular: Air::BasicBlock* successor = m_context.currentBlock->successorBlock(successorIndex); This code in fallsThroughToSuccessor() uses m_context.currentBlock, which will change.

(In reply to comment #78) > Comment on attachment 283935 [details] > the patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=283935&action=review > > > Source/JavaScriptCore/b3/B3BasicBlock.h:123 > > + // This is only valid for Branch and Switch. > > + const FrequentedBlock& fallThrough() const; > > + FrequentedBlock& fallThrough(); > > I understand your rationale for fallThrough() now but I believe stronger > definition is better. > > I don't care a lot. It's fine to keep it if you like fallThrough(). OK. > > > Source/JavaScriptCore/b3/B3LowerToAir.cpp:2443 > > - > > + > > Oops. Fixed. > > > Source/JavaScriptCore/b3/B3Opcode.h:219 > > - > > + > > Oops Fixed. > > > Source/JavaScriptCore/b3/B3Value.h:116 > > + void replaceWithJump(BasicBlock* owner, const FrequentedBlock&); > > + void replaceWithOops(BasicBlock* owner); > > We were more or less avoiding those before. > > There is even a comment: > // Note that the opcode is immutable, except for replacing values with > Identity or Nop. > Opcode opcode() const { return m_opcode; } > > We should remove the comment since we have embraced mutation in a few places. I edited the comment. > > > Source/JavaScriptCore/b3/B3Value.h:237 > > - > > + > > Oops Fixed. > > > Source/JavaScriptCore/b3/air/AirGenerate.cpp:205 > > + context.indexInBlock = UINT_MAX; > > numeric_limits<> is more WebKit-like. We've been using UINT_MAX a lot. It seems to be an exception to the rule. > > > Source/JavaScriptCore/b3/air/AirGenerate.cpp:243 > > - > > + > > Oops. Fixed. > > > Source/JavaScriptCore/b3/air/AirGenerationContext.h:49 > > + unsigned indexInBlock { UINT_MAX }; > > numeric_limits

Landed in https://trac.webkit.org/changeset/203390