Bug 151141 - Implement table-based switches in B3/Air
Summary: Implement table-based switches in B3/Air
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on: 151115
Blocks: 154319 159440
  Show dependency treegraph
 
Reported: 2015-11-11 10:57 PST by Filip Pizlo
Modified: 2016-07-18 18:18 PDT (History)
13 users (show)

See Also:


Attachments
work in progress (23.93 KB, patch)
2016-05-24 09:45 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
close to done (40.13 KB, patch)
2016-05-24 14:15 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
performance (76.72 KB, text/plain)
2016-05-24 18:10 PDT, Filip Pizlo
no flags Details
it works, sort of, but it's the wrong approach (46.41 KB, patch)
2016-05-24 18:10 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
a better approach (45.33 KB, patch)
2016-05-26 10:53 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
I don't even know if it compiles (54.53 KB, patch)
2016-05-27 08:45 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it's getting so bizarre (55.40 KB, patch)
2016-05-27 08:54 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
a bit more (54.56 KB, patch)
2016-05-27 14:33 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (71.50 KB, patch)
2016-05-29 11:31 PDT, Filip Pizlo
buildbot: commit-queue-
Details | Formatted Diff | Diff
Archive of layout-test-results from ews113 for mac-yosemite (1.83 MB, application/zip)
2016-05-29 12:52 PDT, Build Bot
no flags Details
the patch (71.90 KB, patch)
2016-05-29 13:33 PDT, Filip Pizlo
buildbot: commit-queue-
Details | Formatted Diff | Diff
Archive of layout-test-results from ews102 for mac-yosemite (1.32 MB, application/zip)
2016-05-29 18:04 PDT, Build Bot
no flags Details
the patch (74.15 KB, patch)
2016-05-30 10:45 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (69.17 KB, patch)
2016-06-08 13:37 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (69.15 KB, patch)
2016-06-12 20:42 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (69.16 KB, patch)
2016-06-16 14:47 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (69.15 KB, patch)
2016-06-25 20:13 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
rebased patch (69.31 KB, patch)
2016-07-04 10:30 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
a new approach (83.33 KB, patch)
2016-07-04 10:49 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
a bit more (90.07 KB, patch)
2016-07-04 11:37 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
tiny bit more (92.14 KB, patch)
2016-07-04 13:44 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
so fun (98.94 KB, patch)
2016-07-04 13:49 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
a tiny bit more (116.53 KB, patch)
2016-07-05 15:50 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
so small patch (379.99 KB, patch)
2016-07-05 16:07 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
maybe it's done (407.86 KB, patch)
2016-07-05 20:15 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
a bit more (405.59 KB, patch)
2016-07-05 20:18 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
closer to done (411.56 KB, patch)
2016-07-07 14:51 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
made some things compile (414.26 KB, patch)
2016-07-07 15:04 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more compile fixes (415.21 KB, patch)
2016-07-07 15:33 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it seems to work! (418.59 KB, patch)
2016-07-07 20:36 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
maybe done (418.29 KB, patch)
2016-07-08 00:13 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (441.94 KB, patch)
2016-07-08 09:27 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (443.54 KB, patch)
2016-07-08 15:38 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (444.16 KB, patch)
2016-07-08 16:36 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (446.26 KB, patch)
2016-07-10 10:57 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (424.74 KB, patch)
2016-07-18 13:54 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (425.28 KB, patch)
2016-07-18 14:20 PDT, Filip Pizlo
benjamin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2015-11-11 10:57:43 PST
We should do this in B3::lowerMacros(). During the recursive bisecting, if we find a span of case statements that is sufficiently compact, we can optimize it down to an indirect jump.  This can be represented in B3.

- The jump table can be an opaque byproduct that will eventually hold and array of CodeLocationLabels.
- Introduce a new B3 Opcode called AwesomeJump that takes a pointer to jump to and a list of BasicBlocks that are possible successors.
- AwesomeJumps can be compiled to something equivalent in Air.
- CFG simplification ignores AwesomeJumps except when they only have one successor, in which case it can turn them into a Jump.
- A late phase can tell the byproduct holding the jump table that now is a good time to get the addresses of the BasicBlocks.  This will need some kind of hook into Air::generate().
Comment 1 Filip Pizlo 2016-05-24 09:45:49 PDT
Created attachment 279663 [details]
work in progress
Comment 2 Mark Lam 2016-05-24 09:48:57 PDT
(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".
Comment 3 Filip Pizlo 2016-05-24 09:58:14 PDT
(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.
Comment 4 Filip Pizlo 2016-05-24 13:29:20 PDT
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.
Comment 5 Filip Pizlo 2016-05-24 13:35:57 PDT
(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.
Comment 6 Filip Pizlo 2016-05-24 13:49:37 PDT
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.
Comment 7 Filip Pizlo 2016-05-24 14:15:26 PDT
Created attachment 279705 [details]
close to done
Comment 8 Filip Pizlo 2016-05-24 18:10:15 PDT
Created attachment 279733 [details]
performance
Comment 9 Filip Pizlo 2016-05-24 18:10:35 PDT
Created attachment 279734 [details]
it works, sort of, but it's the wrong approach
Comment 10 WebKit Commit Bot 2016-05-24 18:13:21 PDT
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 11 Filip Pizlo 2016-05-26 07:27:42 PDT
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.
Comment 12 Filip Pizlo 2016-05-26 08:18:19 PDT
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.
Comment 13 Mark Lam 2016-05-26 08:21:48 PDT
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.
Comment 14 Filip Pizlo 2016-05-26 08:30:57 PDT
(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.
Comment 15 Filip Pizlo 2016-05-26 10:53:21 PDT
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.
Comment 16 Filip Pizlo 2016-05-26 11:03:19 PDT
(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. ;-)
Comment 17 Filip Pizlo 2016-05-27 08:45:05 PDT
Created attachment 279961 [details]
I don't even know if it compiles
Comment 18 Filip Pizlo 2016-05-27 08:54:26 PDT
Created attachment 279962 [details]
it's getting so bizarre
Comment 19 Filip Pizlo 2016-05-27 14:33:51 PDT
Created attachment 279996 [details]
a bit more
Comment 20 Filip Pizlo 2016-05-29 10:02:52 PDT
(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".
Comment 21 Filip Pizlo 2016-05-29 11:31:10 PDT
Created attachment 280062 [details]
the patch

It works!!!
Comment 22 WebKit Commit Bot 2016-05-29 11:32:29 PDT
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 23 Build Bot 2016-05-29 12:52:27 PDT
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
Comment 24 Build Bot 2016-05-29 12:52:31 PDT
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 25 Filip Pizlo 2016-05-29 13:26:01 PDT
Comment on attachment 280062 [details]
the patch

Investigating debug issues.
Comment 26 Filip Pizlo 2016-05-29 13:29:35 PDT
(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);
Comment 27 Filip Pizlo 2016-05-29 13:33:56 PDT
Created attachment 280064 [details]
the patch

Fixed the debug failures by removing a bogus assertion.
Comment 28 WebKit Commit Bot 2016-05-29 13:35:29 PDT
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 29 Build Bot 2016-05-29 18:04:17 PDT
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.
Comment 30 Build Bot 2016-05-29 18:04:22 PDT
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
Comment 31 Filip Pizlo 2016-05-30 10:45:20 PDT
Created attachment 280103 [details]
the patch
Comment 32 WebKit Commit Bot 2016-05-30 10:47:55 PDT
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.
Comment 33 Filip Pizlo 2016-06-08 13:37:43 PDT
Created attachment 280834 [details]
the patch

Rebased patch
Comment 34 WebKit Commit Bot 2016-06-08 13:39:16 PDT
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.
Comment 35 Filip Pizlo 2016-06-12 20:42:28 PDT
Created attachment 281153 [details]
the patch

rebased
Comment 36 WebKit Commit Bot 2016-06-12 20:44:04 PDT
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.
Comment 37 Filip Pizlo 2016-06-16 14:47:25 PDT
Created attachment 281475 [details]
the patch

Rebased again.
Comment 38 WebKit Commit Bot 2016-06-16 14:49:53 PDT
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.
Comment 39 Filip Pizlo 2016-06-25 20:13:52 PDT
Created attachment 282088 [details]
the patch
Comment 40 WebKit Commit Bot 2016-06-25 20:16:09 PDT
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.
Comment 41 Filip Pizlo 2016-07-03 20:12:28 PDT
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.
Comment 42 Filip Pizlo 2016-07-03 20:27:24 PDT
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.
Comment 43 Filip Pizlo 2016-07-03 21:07:58 PDT
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.
Comment 44 Filip Pizlo 2016-07-03 22:09:34 PDT
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!
Comment 45 Filip Pizlo 2016-07-04 10:30:55 PDT
Created attachment 282728 [details]
rebased patch

Uploading rebased patch before I change the approach to make Patchpoint into a valid terminal.
Comment 46 WebKit Commit Bot 2016-07-04 10:33:01 PDT
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.
Comment 47 Filip Pizlo 2016-07-04 10:49:22 PDT
Created attachment 282730 [details]
a new approach

Starting to remove ControlValue
Comment 48 Filip Pizlo 2016-07-04 11:37:13 PDT
Created attachment 282731 [details]
a bit more

So much fun
Comment 49 Filip Pizlo 2016-07-04 11:39:00 PDT
Comment on attachment 282728 [details]
rebased patch

Looks like this patch wasn't properly rebased.
Comment 50 Filip Pizlo 2016-07-04 13:44:17 PDT
Created attachment 282732 [details]
tiny bit more
Comment 51 Filip Pizlo 2016-07-04 13:49:49 PDT
Created attachment 282733 [details]
so fun

Wow, removing ControlValue lets me remove some nasty garbage, like the weirdo terminal validation in resetReachability().
Comment 52 Filip Pizlo 2016-07-05 15:50:46 PDT
Created attachment 282819 [details]
a tiny bit more

I think that now most of the IR does not care about ControlValue.
Comment 53 Filip Pizlo 2016-07-05 16:07:46 PDT
Created attachment 282823 [details]
so small patch
Comment 54 Filip Pizlo 2016-07-05 20:15:35 PDT
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.
Comment 55 Filip Pizlo 2016-07-05 20:18:32 PDT
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.
Comment 56 Filip Pizlo 2016-07-07 14:51:07 PDT
Created attachment 283054 [details]
closer to done

Fixed up the threaded interpreter test.
Comment 57 Filip Pizlo 2016-07-07 15:04:10 PDT
Created attachment 283059 [details]
made some things compile
Comment 58 Filip Pizlo 2016-07-07 15:33:38 PDT
Created attachment 283067 [details]
more compile fixes
Comment 59 Filip Pizlo 2016-07-07 20:36:46 PDT
Created attachment 283104 [details]
it seems to work!

Still need to run more tests, but so far it seems solid.
Comment 60 Filip Pizlo 2016-07-08 00:13:37 PDT
Created attachment 283113 [details]
maybe done

Seems to work!!
Comment 61 WebKit Commit Bot 2016-07-08 00:15:34 PDT
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.
Comment 62 Filip Pizlo 2016-07-08 09:27:44 PDT
Created attachment 283169 [details]
the patch
Comment 63 WebKit Commit Bot 2016-07-08 09:30:57 PDT
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.
Comment 64 Filip Pizlo 2016-07-08 15:38:43 PDT
Created attachment 283207 [details]
the patch
Comment 65 WebKit Commit Bot 2016-07-08 15:42:11 PDT
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.
Comment 66 Filip Pizlo 2016-07-08 16:36:15 PDT
Created attachment 283217 [details]
the patch
Comment 67 WebKit Commit Bot 2016-07-08 16:38:34 PDT
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.
Comment 68 Filip Pizlo 2016-07-10 10:57:00 PDT
Created attachment 283288 [details]
the patch
Comment 69 WebKit Commit Bot 2016-07-10 10:59:36 PDT
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 70 Benjamin Poulain 2016-07-18 13:32:55 PDT
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.
Comment 71 Filip Pizlo 2016-07-18 13:47:59 PDT
(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) {
Comment 72 Filip Pizlo 2016-07-18 13:54:55 PDT
Created attachment 283928 [details]
the patch

Addressed Ben's feedback
Comment 73 Filip Pizlo 2016-07-18 13:56:41 PDT
> > 
> > > 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.
Comment 74 WebKit Commit Bot 2016-07-18 13:57:41 PDT
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.
Comment 75 Filip Pizlo 2016-07-18 14:20:28 PDT
Created attachment 283935 [details]
the patch

Fixed the bug with LowerMacros using cases.size() where it meant end-begin.
Comment 76 WebKit Commit Bot 2016-07-18 14:22:08 PDT
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 77 Geoffrey Garen 2016-07-18 16:28:08 PDT
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 78 Benjamin Poulain 2016-07-18 16:29:16 PDT
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
Comment 79 Filip Pizlo 2016-07-18 16:31:29 PDT
(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.
Comment 80 Filip Pizlo 2016-07-18 16:34:46 PDT
(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
Comment 81 Filip Pizlo 2016-07-18 18:18:19 PDT
Landed in https://trac.webkit.org/changeset/203390