Add support to optionally limit the size of jump tables

[evandro]

Summary

Many high-performance processors have a dedicated branch predictor for indirect branches, commonly used with jump tables. As sophisticated as such branch predictors are, they tend to have well defined limits beyond which their effectiveness is hampered or even nullified. One such limit is the number of possible destinations for a given indirect branches that such branch predictors can handle.

This patch considers a limit that a target may set to the number of destination addresses in a jump table.

[rengolin]

How hard would be to write tests to these?

[evandro]

@rengolin, it depends if it's on a Friday before a holiday...

Seriously, though. I'm working on them.

[hans]

I'm not super familiar with branch predictors, but this does raise some questions.

The first is how you're planning to use this. It seems your patch only exposes this as two command-line options, something which is typically only used for debugging. Should the various targets have default values for this?

This also seems to be pretty a tricky trade-off between having a single indirect branch, or multiple direct and indirect branches. The latter puts more pressure on the CPU in terms of how many branches it has to track.

I assume you have some benchmark in mind where this is profitable?

I guess what I'm saying is that if the set of destinations is dense, building a jump table seems like a good choice in general, and breaking it up seems like a pretty CPU- and work-load specific tuning that I'm not sure the compiler should be doing.

[evandro]

@hans, what happens is that is the jump table is too large, many entries cannot be predicted and lead to thrashing of the indirect branch predictor. Increasing the mix of direct and indirect branches, as this patch promotes, allows both the direct branch predictor and the indirect branch predictor to yield an overall lower branch mispredict ratio. And, given that the cost of a mispredict may be vastly larger than the cost of computing, I observed an overall gain, remarkably in some benchmarks involving parsing.

[hans]

Sure, I can see the benefit of this transformation, but I'm worried that it will be hard for the compiler to get right, as whether it's profitable or not depends on the micro-architecture and the run-time dynamics of the switch.

[evandro]

@hans, indeed, this change leaves it up to the targets to tune the limit for jump tables.

[evandro]

• Remove the option to specify the lower limit for jump tables.
• Make the option to specify the upper limit for jump tables generic.
• Add test case.

[evandro]

Ping^1

[hans]

Sorry for the slow reply; I was on vacation.

I can certainly see that this will be beneficial to some codes on certain architectures.

My concern is whether the added complexity is worth it, as the code for building jump tables is already complicated. I now see that you've set a default value for a single AArch64 micro-architecture, ExynosM1. Does that single target justify the added complexity for all other targets that don't use this?

+Tim since he owns AArch64. I'd be interesting to hear what he thinks about the general value of this.

[evandro]

In D21940#487082, @hans wrote:

My concern is whether the added complexity is worth it, as the code for building jump tables is already complicated. I now see that you've set a default value for a single AArch64 micro-architecture, ExynosM1. Does that single target justify the added complexity for all other targets that don't use this?

Yes. On M1, this patch improves 253.perlbmk or 400.perlbench by up to 15% and up to 10% in private benchmarks. However, I'm rather positive that other micro architectures may benefit from this change as well, since indirect branch prediction is typically more limited and thus less accurate than direct branch prediction.

FWIW, it the sub target doesn't override the default limit, the algorithm iterates as many times as before.

[t.p.northover]

Tim since he owns AArch64. I'd be interesting to hear what he thinks about the general value of this.

I can't really comment on the performance changes, but it doesn't really seem to add much complexity. It seems pretty natural that if the minimum size is tuneable, the maximum ought to be.

[hans]

In D21940#488792, @t.p.northover wrote:

Tim since he owns AArch64. I'd be interesting to hear what he thinks about the general value of this.

I can't really comment on the performance changes, but it doesn't really seem to add much complexity. It seems pretty natural that if the minimum size is tuneable, the maximum ought to be.

I hate to disagree, but I do think this adds complexity. In fact, I'm not convinced that the algorithm as modified by the patch actually works (see comment). If it does, I'd like to see some test cases demonstrating it.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8383 ↗

(On Diff #62799)

why the variable renaming?

8386 ↗

(On Diff #62799)

i suppose this is now Clusters[k]?

8401 ↗

(On Diff #62799)

This splits Clusters[i..j] into MaxJumpTableSize-sized tables. But there's no guarantee that each such table would be dense enough for a jump table.

It could be that a range of 2 * MaxJumpTableSize clusters is only dense enough as a whole, and if it's split up as this code would do, the parts would not be dense enough for jump tables.

With this change, I don't think the algorithm finds the optimal partitioning given the density, min- and max-size criteria.

[evandro]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8383 ↗

(On Diff #62799)

I believe that it improves the legibility of the code.

8386 ↗

(On Diff #62799)

Aye.

8401 ↗

(On Diff #62799)

Allow me to investigate this.

[hans]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8396 ↗

(On Diff #62799)

Actually, probably all that's needed would be to add a '&& l - k <= MaxJumpTableSize' here. I think that would allow the algorithm to find optimal partitionings given minsize, maxsize and density, and it seems like a straight-forward change so not adding too much complexity.

This also needs better testing, including a check for optsize and some non-straight forward case. I don't think the current test works as the default target may or may not like jump tables; probably better to use test/CodeGen/X86/switch.ll

[evandro]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8396 ↗

(On Diff #62799)

That condition limits the splitting unnecessarily. Perhaps isDense(Clusters, &TotalCases[0], i, j, MinDensity) would suffice to guarantee density, even if not without side effects.

[hans]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8396 ↗

(On Diff #62799)

Can you elaborate on "That condition limits the splitting unnecessarily"?

Isn't limiting the partitioning so the jump tables are <= the max size what you want here?

[evandro]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8396 ↗

(On Diff #62799)

I should have said that it increases the splitting unnecessarily, at least in simple, perfectly dense tests. I think that this happens by limiting the clusters that the loop visits, thus limiting the number of optimal solutions.

[evandro]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8396 ↗

(On Diff #62799)

After giving this more thought, I think that the proposed patch does guarantee that the smaller tables are dense.

Given that the set [k, j] is dense, it follows that the maximum table size is j + 1 - k. Since j + 1 is k, the test l - i is correct.

[hans]

Here's an example where the proposed patch doesn't work:

declare void @g(i32)

define void @test(i32 %x) {
entry:
  switch i32 %x, label %return [
    i32 1, label %bb1
    i32 2, label %bb2
    i32 3, label %bb3
    i32 4, label %bb4

    i32 14, label %bb5
    i32 15, label %bb6
  ]
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
bb5: tail call void @g(i32 5) br label %return
bb6: tail call void @g(i32 6) br label %return
return: ret void
}

When run with

$ llc -mtriple=x86_64-linux-gnu -jump-table-density=40 -max-jump-table=4 a.ll -o -

it will decide the 1-15 jump table is too big, but fail to create a jump table for cases 1-4.

I believe the correct way to do this is something like https://reviews.llvm.org/differential/diff/66883/ and I'm not sure I understand where it would split things unnecessarily.

[evandro]

I'm confused about the change to the table density in the command line. Why did you deem it necessary?

Thank you.

[hans]

In D21940#507517, @evandro wrote:

I'm confused about the change to the table density in the command line. Why did you deem it necessary?

To make it more explicit which minimum jump table density my example was tailored for (40% is default for optsize, 10% otherwise). The switch in my example has 40% density, but your code will split off cases 3, 4, 14, 15 from that which falls below the threshold.

The example can of course be adjusted to show the problem at any density threshold.

[evandro]

In D21940#508684, @hans wrote:

The example can of course be adjusted to show the problem at any density threshold.

I think that I understand it better. I'll devise a better solution.

On a side note, I suspect that I should also examine findBitTestClusters() to enforce both MinimumJumpTableEntries and MaximumJumpTableEntries, yes?

[hans]

In D21940#508704, @evandro wrote:

On a side note, I suspect that I should also examine findBitTestClusters() to enforce both MinimumJumpTableEntries and MaximumJumpTableEntries, yes?

Why? findBitTestClusters() doesn't build jump tables.

[evandro]

In D21940#508705, @hans wrote:

Why? findBitTestClusters() doesn't build jump tables.

Of course not. It never calls buildJumpTable(). :-}

[hans]

It looks like this is essentially what I proposed in https://reviews.llvm.org/differential/diff/66883/, except you're taking into account the "gaps" in the jump table when enforcing the maximum size.

It seems unfortunate that getMinimumJumpTableEntries() and getMaximumJumpTableSize() are now using different units of measurement.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8390 ↗

(On Diff #71701)

All these unrelated changes are making the patch much harder to review. I also don't think they're improving anything.

I assume you changed this because you didn't like i being a signed type? And then "i >= 0" doesn't work anymore, so now you check "i > 0" and use "i - 1" everywhere, which is hard to read, in my opinion.

8428 ↗

(On Diff #71701)

What was wrong with this one?

[evandro]

In D21940#545345, @hans wrote:

It seems unfortunate that getMinimumJumpTableEntries() and getMaximumJumpTableSize() are now using different units of measurement.

Indeed, but I'm afraid that it's necessary.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8390 ↗

(On Diff #71701)

I meant to make sure to use data types consistently.

8428 ↗

(On Diff #71701)

Err... purely stylistic. :-}

[hans]

In D21940#545354, @evandro wrote:

In D21940#545345, @hans wrote:

It seems unfortunate that getMinimumJumpTableEntries() and getMaximumJumpTableSize() are now using different units of measurement.

Indeed, but I'm afraid that it's necessary.

Can you elaborate on why it's necessary?

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8390 ↗

(On Diff #71701)

Oh, you mean because N is unsigned? That makes some sense I suppose, but here I think it hurts readability. int64_t is wider than unsigned, so there is no risk of losing precision, and it allows us to iterate 'i' all the way down to 0.

[evandro]

In D21940#545362, @hans wrote:

In D21940#545354, @evandro wrote:

In D21940#545345, @hans wrote:

It seems unfortunate that getMinimumJumpTableEntries() and getMaximumJumpTableSize() are now using different units of measurement.

Indeed, but I'm afraid that it's necessary.

Can you elaborate on why it's necessary?

getMinimumJumpTableEntries() is actually the lower limit for the number of cases to be considered for a jump table. getMaximumJumpTableSize() is the upper limit for the number of rows in a jump table.

[evandro]

In D21940#545376, @evandro wrote:

In D21940#545362, @hans wrote:

In D21940#545354, @evandro wrote:

In D21940#545345, @hans wrote:

It seems unfortunate that getMinimumJumpTableEntries() and getMaximumJumpTableSize() are now using different units of measurement.

Indeed, but I'm afraid that it's necessary.

Can you elaborate on why it's necessary?

getMinimumJumpTableEntries() is actually the lower limit for the number of cases to be considered for a jump table. getMaximumJumpTableSize() is the upper limit for the number of rows in a jump table.

Here's another thought: the difference in what the minimum limit specifies and what the maximum limit specifies is because the former applies to the input conditions and the latter, to the output. Then, perhaps the name of the methods might be changed to getMinimumJumpTableInputEntries() and getMaximumJumpTableOutputEntries(), or something along this line.

[hans]

In D21940#546395, @evandro wrote:

getMinimumJumpTableEntries() is actually the lower limit for the number of cases to be considered for a jump table. getMaximumJumpTableSize() is the upper limit for the number of rows in a jump table.

Here's another thought: the difference in what the minimum limit specifies and what the maximum limit specifies is because the former applies to the input conditions and the latter, to the output. Then, perhaps the name of the methods might be changed to getMinimumJumpTableInputEntries() and getMaximumJumpTableOutputEntries(), or something along this line.

Hmm, no I think that's more confusing. getMinimumJumpTableEntries() and getMaximumJumpTableSize() seem fine the more I think about it.

I feel like this code review is dragging out. Let me summarize my position here so we can get it committed:

• I'm OK with the idea of enforcing a maximum jump table size, even if it's just used by default on some specific target.
• I think the correct way to do it is just adding a "foo <= MaxSize" check in addition to the isDense() check, as you've done in the latest version
• The new TotalGaps vector seems unnecessary. It should be possible to compute the JumpTableSize in constant time by looking at Low and High of the first and last cluster. Potentially this could be done with a small helper function similar to isDense.
• Please remove all the unrelated changes; they make this patch much more intrusive than it should be.

[evandro]

In D21940#548881, @hans wrote:

• The new TotalGaps vector seems unnecessary. It should be possible to compute the JumpTableSize in constant time by looking at Low and High of the first and last cluster. Potentially this could be done with a small helper function similar to isDense.

I'm not sure that it's equivalent, since each element in TotalGaps[] is the sum of of the gaps up to that element. Or am I missing something?

• Please remove all the unrelated changes; they make this patch much more intrusive than it should be.

Will do.

[evandro]

Tried to minimize ancillary changes. Please, let me know if I missed any.

[evandro]

Really updating the patch this time... :-}

[hans]

In D21940#549056, @evandro wrote:

In D21940#548881, @hans wrote:

• The new TotalGaps vector seems unnecessary. It should be possible to compute the JumpTableSize in constant time by looking at Low and High of the first and last cluster. Potentially this could be done with a small helper function similar to isDense.

I'm not sure that it's equivalent, since each element in TotalGaps[] is the sum of of the gaps up to that element. Or am I missing something?

Sure, but you use TotalGaps[] together with TotalCases[] to compute the size of the jump table:

unsigned JumpTableSize = TotalCases[j] - TotalCases[i - 1] +
                         TotalGaps[j] - TotalGaps[i - 1];

I'm saying you can compute the equivalent just by doing Clusters[j].High - Clusters[i].Low + 1.

In D21940#549062, @evandro wrote:

Tried to minimize ancillary changes. Please, let me know if I missed any.

I still see lots, just look at the diff.

You're still changing N and the loop indices to unsigned. The comment for TotalCases, and the code to initialize it has changed, you're switching to pre-increment in the loops, ...

[evandro]

In D21940#549096, @hans wrote:

I'm not sure that it's equivalent, since each element in TotalGaps[] is the sum of of the gaps up to that element. Or am I missing something?

Sure, but you use TotalGaps[] together with TotalCases[] to compute the size of the jump table:

unsigned JumpTableSize = TotalCases[j] - TotalCases[i - 1] +
                         TotalGaps[j] - TotalGaps[i - 1];

I'm saying you can compute the equivalent just by doing Clusters[j].High - Clusters[i].Low + 1.

Clusters[i] or Clusters[i - 1] in this patch?

Besides, TotalGaps[] is also used at TotalCases[N - 1] + TotalGaps[N - 1] <= MaxJumpTableSize.

You're still changing N and the loop indices to unsigned.

I think that it's better practice to use data types consistently.

The comment for TotalCases, and the code to initialize it has changed, you're switching to pre-increment in the loops, ...

OK.

[hans]

In D21940#549103, @evandro wrote:

In D21940#549096, @hans wrote:

I'm not sure that it's equivalent, since each element in TotalGaps[] is the sum of of the gaps up to that element. Or am I missing something?

Sure, but you use TotalGaps[] together with TotalCases[] to compute the size of the jump table:

unsigned JumpTableSize = TotalCases[j] - TotalCases[i - 1] +
                         TotalGaps[j] - TotalGaps[i - 1];

I'm saying you can compute the equivalent just by doing Clusters[j].High - Clusters[i].Low + 1.

Clusters[i] or Clusters[i - 1] in this patch?

Clusters[i] as the loop is formulated in trunk.

Besides, TotalGaps[] is also used at TotalCases[N - 1] + TotalGaps[N - 1] <= MaxJumpTableSize.

The same computation can be used there. Maybe break it out to a helper function similar to isDense.

You're still changing N and the loop indices to unsigned.

I think that it's better practice to use data types consistently.

As I already pointed out, I think this change reduces readability and is unrelated to enforcing a maximum size on the jump tables.

[evandro]

In D21940#549128, @hans wrote:

In D21940#549103, @evandro wrote:

In D21940#549096, @hans wrote:

I'm not sure that it's equivalent, since each element in TotalGaps[] is the sum of of the gaps up to that element. Or am I missing something?

Sure, but you use TotalGaps[] together with TotalCases[] to compute the size of the jump table:

unsigned JumpTableSize = TotalCases[j] - TotalCases[i - 1] +
                         TotalGaps[j] - TotalGaps[i - 1];

I'm saying you can compute the equivalent just by doing Clusters[j].High - Clusters[i].Low + 1.

Clusters[i] or Clusters[i - 1] in this patch?

Clusters[i] as the loop is formulated in trunk.

Besides, TotalGaps[] is also used at TotalCases[N - 1] + TotalGaps[N - 1] <= MaxJumpTableSize.

The same computation can be used there. Maybe break it out to a helper function similar to isDense.

I tried changing it but, IIUC, the test cases below fail to pass.

You're still changing N and the loop indices to unsigned.

I think that it's better practice to use data types consistently.

As I already pointed out, I think this change reduces readability and is unrelated to enforcing a maximum size on the jump tables.

Out of curiosity: would such changes be suitable for a follow up NFC patch?

[hans]

In D21940#549131, @evandro wrote:

In D21940#549128, @hans wrote:

In D21940#549103, @evandro wrote:

In D21940#549096, @hans wrote:

I'm not sure that it's equivalent, since each element in TotalGaps[] is the sum of of the gaps up to that element. Or am I missing something?

Sure, but you use TotalGaps[] together with TotalCases[] to compute the size of the jump table:

unsigned JumpTableSize = TotalCases[j] - TotalCases[i - 1] +
                         TotalGaps[j] - TotalGaps[i - 1];

I'm saying you can compute the equivalent just by doing Clusters[j].High - Clusters[i].Low + 1.

Clusters[i] or Clusters[i - 1] in this patch?

Clusters[i] as the loop is formulated in trunk.

Besides, TotalGaps[] is also used at TotalCases[N - 1] + TotalGaps[N - 1] <= MaxJumpTableSize.

The same computation can be used there. Maybe break it out to a helper function similar to isDense.

I tried changing it but, IIUC, the test cases below fail to pass.

Then there must be a bug somewhere.

You're still changing N and the loop indices to unsigned.

I think that it's better practice to use data types consistently.

As I already pointed out, I think this change reduces readability and is unrelated to enforcing a maximum size on the jump tables.

Out of curiosity: would such changes be suitable for a follow up NFC patch?

That would be the way to propose such a change, yes, but I'm still not keen on the idea.

[evandro]

Fewer ancillary changes.

[evandro]

Sigh... it's been a long day.

[evandro]

In D21940#549148, @hans wrote:

Then there must be a bug somewhere.

As usual, the issue of being off by one.

[evandro]

Eliminated TotalGaps[].

[hans]

Thanks for the update! This is starting to look much better now.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8338 ↗

(On Diff #72113)

I prefer the old comment as it explains specifically what the element at index i represents.

8342 ↗

(On Diff #72113)

No need to change the contents of this for-loop.

8352 ↗

(On Diff #72113)

What do you think about introducing a helper function that we could call like 'jumpTableSize(Clusters, 0, N-1)'? I think that would make this a little easier to read here and below, and in the function we could take care not to let the value overflow for example.

8398 ↗

(On Diff #72113)

This could overflow. It would be benign because a jump table of size 2^32 or 2^64 is not likely to be dense (if it is, we have other problems), but maybe we should be doing '.getLimitedValue(UINT_MAX - 1)' to make it saturate instead of overflow.

8401 ↗

(On Diff #72113)

This line looks like an unrelated change.

8403 ↗

(On Diff #72113)

These two lines look like an unrelated change.

8408 ↗

(On Diff #72113)

Why do we need this extra check? We're already guaranteed by the above that there won't be any tables greater than the max size.

llvm/test/CodeGen/Generic/max-jump-table.ll

1 ↗

(On Diff #72113)

Running llc without a target triple might end up running for a target that doesn't do jump tables for switches.

I think this test needs to be under a target that we know uses jump tables. If you target ARM you can also test that ExynosM1 does get its desired max jump table size.

[hans]

I just realized the llvm-commits list wasn't cc'd.

[evandro]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8342 ↗

(On Diff #72113)

Like JumpTableSize, can't this overflow too?

8352 ↗

(On Diff #72113)

The operation seemed too short for a function, but saturating its return might make sense wrapping this in a function.

8408 ↗

(On Diff #72113)

This extra check is for backwards compatibility. Though the table is no larger than MaxJumpTableSize, we may end up with two tables rather than one. It might make sense to increase tables slightly to decrease the length of the if-then-else chain at the beginning, but when the size of the tables is limited, we might end up with a longer if-then-else chain, because tables smaller than MinJumpTableEntries would be more likely. As a matter of fact, except to improve code size, it'd be better to create fewer jump tables, if it adds links to the if-then--else chain, as most processors can predict the outcome of each link better than of an indirect branch. Without this condition, max-jump-table.ll below fails at the jt1 function and the resulting code is 3 jump tables with a 3 comparisons instead of 2 jump tables with 3 comparisons.

llvm/test/CodeGen/Generic/max-jump-table.ll

1 ↗

(On Diff #72113)

True that.

[evandro]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8352 ↗

(On Diff #72113)

It turns out that CaseClusterVector is a private type of SelectionDAGBuilder. In order to minimize the changes by this patch, I'll repeat the code as needed.

[hans]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8344 ↗

(On Diff #72197)

I don't think it can in practice, at least not currently. Each Cluster is created by merging consecutive case-statements with the same destination. So there would have to be an impractically large amount of case-statements to end up with a Cluster where High - Low would overflow.

For the table size however, it's enough to have one "case 0" and one "case UINT64_MAX" to generate a large potential table size. Now, we would obviously never build such a large table, but we would do the size computation, for example in isDense().

8353 ↗

(On Diff #72197)

No problem, I think this turned out pretty well too.

8411–8412 ↗

(On Diff #72197)

Hmm. I don't like this.

The point of this algorithm is to find jump tables given the size and density criteria. It sounds like your code wants to go the other way.

Also, your code doesn't make us choose the partitioning with the least amount of jump tables, it only removes the code that makes us choose the one with most jump tables, which means we'll end up choosing whichever partitioning that comes first.

So it seems the jt1 function is just getting lucky here.

And in general, picking the partitioning with more jump tables is important here. It's possible to construct a test case with two possible partitionings of equal size, where one results in no jump tables and a very bad lowering.

llvm/test/CodeGen/Generic/max-jump-table.ll

2 ↗

(On Diff #72197)

I think the test also needs to move from CodeGen/Generic to CodeGen/AArch64.

The tests under Generic/ will be run in builds which may not have the AArch64 target.

[evandro]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8344 ↗

(On Diff #72197)

I see.

8411–8412 ↗

(On Diff #72197)

I don't feel strongly about it. I'll revert it.

llvm/test/CodeGen/Generic/max-jump-table.ll

2 ↗

(On Diff #72197)

True that.

[hans]

lgtm

llvm/trunk/include/llvm/Target/TargetLowering.h

bool usesUnderscoreSetJmp() const {
     return UseUnderscoreSetJmp;
   }
 
   /// Determine if we should use _longjmp or longjmp to implement llvm.longjmp.
   bool usesUnderscoreLongJmp() const {
     return UseUnderscoreLongJmp;
   }
 
-  /// Return integer threshold on number of blocks to use jump tables rather
-  /// than if sequence.
-  int getMinimumJumpTableEntries() const {
+  /// Return lower limit for number of blocks in a jump table.
+  unsigned getMinimumJumpTableEntries() const {
     return MinimumJumpTableEntries;
   }
 
+  /// Return upper limit for number of entries in a jump table.
+  /// Zero if no limit.
+  unsigned getMaximumJumpTableSize() const;
+
   /// If a physical register, this specifies the register that
   /// llvm.savestack/llvm.restorestack should save and restore.
   unsigned getStackPointerRegisterToSaveRestore() const {
     return StackPointerRegisterToSaveRestore;
   }
 
   /// If a physical register, this returns the register that receives the
   /// exception address on entry to an EH pad.
protected:
   }
 
   /// Indicate whether this target prefers to use _longjmp to implement
   /// llvm.longjmp or the version without _.  Defaults to false.
   void setUseUnderscoreLongJmp(bool Val) {
     UseUnderscoreLongJmp = Val;
   }
 
-  /// Indicate the number of blocks to generate jump tables rather than if
-  /// sequence.
-  void setMinimumJumpTableEntries(int Val) {
+  /// Indicate the minimum number of blocks to generate jump tables.
+  void setMinimumJumpTableEntries(unsigned Val) {
     MinimumJumpTableEntries = Val;
   }
 
+  /// Indicate the maximum number of entries in jump tables.
+  /// Set to zero to generate unlimited jump tables.
+  void setMaximumJumpTableSize(unsigned);
+
   /// If set to a physical register, this specifies the register that
   /// llvm.savestack/llvm.restorestack should save and restore.
   void setStackPointerRegisterToSaveRestore(unsigned R) {
     StackPointerRegisterToSaveRestore = R;
   }
 
   /// Tells the code generator not to expand operations into sequences that use
   /// the select operations if possible.

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

#ifndef NDEBUG
   for (unsigned i = 1, e = Clusters.size(); i < e; ++i)
     assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue()));
 #endif
 
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   if (!areJTsAllowed(TLI, SI))
     return;
 
+  const bool OptForSize = DefaultMBB->getParent()->getFunction()->optForSize();
+
   const int64_t N = Clusters.size();
-  const unsigned MinJumpTableSize = TLI.getMinimumJumpTableEntries();
+  const unsigned MinJumpTableEntries = TLI.getMinimumJumpTableEntries();
+  const unsigned MaxJumpTableSize =
+    OptForSize ? UINT_MAX : TLI.getMaximumJumpTableSize() ?
+                            TLI.getMaximumJumpTableSize() : UINT_MAX;
+
+  if (N < 2 || N < MinJumpTableEntries)
+    return;
 
   // TotalCases[i]: Total nbr of cases in Clusters[0..i].
   SmallVector<unsigned, 8> TotalCases(N);
-
   for (unsigned i = 0; i < N; ++i) {
     const APInt &Hi = Clusters[i].High->getValue();
     const APInt &Lo = Clusters[i].Low->getValue();
     TotalCases[i] = (Hi - Lo).getLimitedValue() + 1;
     if (i != 0)
       TotalCases[i] += TotalCases[i - 1];
   }
 
-  unsigned MinDensity = JumpTableDensity;
-  if (DefaultMBB->getParent()->getFunction()->optForSize())
-    MinDensity = OptsizeJumpTableDensity;
-  if (N >= MinJumpTableSize
-      && isDense(Clusters, TotalCases, 0, N - 1, MinDensity)) {
-    // Cheap case: the whole range might be suitable for jump table.
+  const unsigned MinDensity =
+    OptForSize ? OptsizeJumpTableDensity : JumpTableDensity;
+
+  // Cheap case: the whole range may be suitable for jump table.
+  unsigned JumpTableSize = (Clusters[N - 1].High->getValue() -
+                            Clusters[0].Low->getValue())
+                           .getLimitedValue(UINT_MAX - 1) + 1;
+  if (JumpTableSize <= MaxJumpTableSize &&
+      isDense(Clusters, TotalCases, 0, N - 1, MinDensity)) {
+
     CaseCluster JTCluster;
     if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) {
       Clusters[0] = JTCluster;
       Clusters.resize(1);
       return;
     }
   }
 
#endif
   // LastElement[i] is the last element of the partition starting at i.
   SmallVector<unsigned, 8> LastElement(N);
   // NumTables[i]: nbr of >= MinJumpTableSize partitions from Clusters[i..N-1].
   SmallVector<unsigned, 8> NumTables(N);
 
   // Base case: There is only one way to partition Clusters[N-1].
   MinPartitions[N - 1] = 1;
   LastElement[N - 1] = N - 1;
-  assert(MinJumpTableSize > 1);
   NumTables[N - 1] = 0;
 
   // Note: loop indexes are signed to avoid underflow.
   for (int64_t i = N - 2; i >= 0; i--) {
     // Find optimal partitioning of Clusters[i..N-1].
     // Baseline: Put Clusters[i] into a partition on its own.
     MinPartitions[i] = MinPartitions[i + 1] + 1;
     LastElement[i] = i;
     NumTables[i] = NumTables[i + 1];
 
     // Search for a solution that results in fewer partitions.
     for (int64_t j = N - 1; j > i; j--) {
       // Try building a partition from Clusters[i..j].
-      if (isDense(Clusters, TotalCases, i, j, MinDensity)) {
+      JumpTableSize = (Clusters[j].High->getValue() -
+                       Clusters[i].Low->getValue())
+                      .getLimitedValue(UINT_MAX - 1) + 1;
+      if (JumpTableSize <= MaxJumpTableSize &&
+          isDense(Clusters, TotalCases, i, j, MinDensity)) {
         unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
-        bool IsTable = j - i + 1 >= MinJumpTableSize;
+        bool IsTable = j - i + 1 >= MinJumpTableEntries;
         unsigned Tables = IsTable + (j == N - 1 ? 0 : NumTables[j + 1]);
 
         // If this j leads to fewer partitions, or same number of partitions
         // with more lookup tables, it is a better partitioning.
         if (NumPartitions < MinPartitions[i] ||
             (NumPartitions == MinPartitions[i] && Tables > NumTables[i])) {
           MinPartitions[i] = NumPartitions;
           LastElement[i] = j;
           NumTables[i] = Tables;
         }
       }
     }
   }
 
   // Iterate over the partitions, replacing some with jump tables in-place.
   unsigned DstIndex = 0;
   for (unsigned First = 0, Last; First < N; First = Last + 1) {
     Last = LastElement[First];
     assert(Last >= First);
     assert(DstIndex <= First);
     unsigned NumClusters = Last - First + 1;
 
     CaseCluster JTCluster;
-    if (NumClusters >= MinJumpTableSize &&
+    if (NumClusters >= MinJumpTableEntries &&
         buildJumpTable(Clusters, First, Last, SI, DefaultMBB, JTCluster)) {
       Clusters[DstIndex++] = JTCluster;
     } else {
       for (unsigned I = First; I <= Last; ++I)
         std::memmove(&Clusters[DstIndex++], &Clusters[I], sizeof(Clusters[I]));
     }
   }
   Clusters.resize(DstIndex);

llvm/trunk/lib/CodeGen/TargetLoweringBase.cpp

 #include <cctype>
 using namespace llvm;
 
 static cl::opt<bool> JumpIsExpensiveOverride(
     "jump-is-expensive", cl::init(false),
     cl::desc("Do not create extra branches to split comparison logic."),
     cl::Hidden);
 
+static cl::opt<unsigned> MaximumJumpTableSize
+  ("max-jump-table", cl::init(0), cl::Hidden,
+   cl::desc("Set maximum number of jump table entries; zero for no limit."));
+
 // Although this default value is arbitrary, it is not random. It is assumed
 // that a condition that evaluates the same way by a higher percentage than this
 // is best represented as control flow. Therefore, the default value N should be
 // set such that the win from N% correct executions is greater than the loss
 // from (100 - N)% mispredicted executions for the majority of intended targets.
 static cl::opt<int> MinPercentageForPredictableBranch(
     "min-predictable-branch", cl::init(99),
     cl::desc("Minimum percentage (0-100) that a condition must be either true "

 // TODO: add LOAD_STACK_GUARD support.
 Value *TargetLoweringBase::getSDagStackGuard(const Module &M) const {
   return M.getGlobalVariable("__stack_chk_guard", true);
 }
 
 Value *TargetLoweringBase::getSSPStackGuardCheck(const Module &M) const {
   return nullptr;
 }
+
+unsigned TargetLoweringBase::getMaximumJumpTableSize() const {
+  return MaximumJumpTableSize;
+}
+
+void TargetLoweringBase::setMaximumJumpTableSize(unsigned Val) {
+  MaximumJumpTableSize = Val;
+}

llvm/trunk/lib/Target/AArch64/AArch64ISelLowering.cpp

AArch64TargetLowering::AArch64TargetLowering(const TargetMachine &TM,
   EnableExtLdPromotion = true;
 
   // Set required alignment.
   setMinFunctionAlignment(2);
   // Set preferred alignments.
   setPrefFunctionAlignment(STI.getPrefFunctionAlignment());
   setPrefLoopAlignment(STI.getPrefLoopAlignment());
 
+  // Only change the limit for entries in a jump table if specified by
+  // the subtarget, but not at the command line.
+  unsigned MaxJT = STI.getMaximumJumpTableSize();
+  if (MaxJT && getMaximumJumpTableSize() == 0)
+    setMaximumJumpTableSize(MaxJT);
+
   setHasExtractBitsInsn(true);
 
   setOperationAction(ISD::INTRINSIC_WO_CHAIN, MVT::Other, Custom);
 
   if (Subtarget->hasNEON()) {
     // FIXME: v1f64 shouldn't be legal if we can avoid it, because it leads to
     // silliness like this:
     setOperationAction(ISD::FABS, MVT::v1f64, Expand);

llvm/trunk/lib/Target/AArch64/AArch64Subtarget.h

protected:
   uint8_t MaxInterleaveFactor = 2;
   uint8_t VectorInsertExtractBaseCost = 3;
   uint16_t CacheLineSize = 0;
   uint16_t PrefetchDistance = 0;
   uint16_t MinPrefetchStride = 1;
   unsigned MaxPrefetchIterationsAhead = UINT_MAX;
   unsigned PrefFunctionAlignment = 0;
   unsigned PrefLoopAlignment = 0;
+  unsigned MaxJumpTableSize = 0;
 
   // ReserveX18 - X18 is not available as a general purpose register.
   bool ReserveX18;
 
   bool IsLittle;
 
   /// CPUString - String name of used CPU.
   std::string CPUString;
public:
   unsigned getPrefetchDistance() const { return PrefetchDistance; }
   unsigned getMinPrefetchStride() const { return MinPrefetchStride; }
   unsigned getMaxPrefetchIterationsAhead() const {
     return MaxPrefetchIterationsAhead;
   }
   unsigned getPrefFunctionAlignment() const { return PrefFunctionAlignment; }
   unsigned getPrefLoopAlignment() const { return PrefLoopAlignment; }
 
+  unsigned getMaximumJumpTableSize() const { return MaxJumpTableSize; }
+
   /// CPU has TBI (top byte of addresses is ignored during HW address
   /// translation) and OS enables it.
   bool supportsAddressTopByteIgnored() const;
 
   bool hasPerfMon() const { return HasPerfMon; }
   bool hasFullFP16() const { return HasFullFP16; }
   bool hasSPE() const { return HasSPE; }
 

llvm/trunk/lib/Target/AArch64/AArch64Subtarget.cpp

case Cyclone:
     MaxPrefetchIterationsAhead = 3;
     break;
   case CortexA57:
     MaxInterleaveFactor = 4;
     break;
   case ExynosM1:
     PrefFunctionAlignment = 4;
     PrefLoopAlignment = 3;
+    MaxJumpTableSize = 12;
     break;
   case Kryo:
     MaxInterleaveFactor = 4;
     VectorInsertExtractBaseCost = 2;
     CacheLineSize = 128;
     PrefetchDistance = 740;
     MinPrefetchStride = 1024;
     MaxPrefetchIterationsAhead = 11;

llvm/trunk/test/CodeGen/AArch64/max-jump-table.ll

+; RUN: llc %s -O2 -print-machineinstrs -march=aarch64 -jump-table-density=40                   -o - 2>%t; FileCheck %s --check-prefixes=CHECK,CHECK0  <%t
+; RUN: llc %s -O2 -print-machineinstrs -march=aarch64 -jump-table-density=40 -max-jump-table=4 -o - 2>%t; FileCheck %s --check-prefixes=CHECK,CHECK4  <%t
+; RUN: llc %s -O2 -print-machineinstrs -march=aarch64 -jump-table-density=40 -max-jump-table=8 -o - 2>%t; FileCheck %s --check-prefixes=CHECK,CHECK8  <%t
+; RUN: llc %s -O2 -print-machineinstrs -march=aarch64 -jump-table-density=40 -mcpu=exynos-m1   -o - 2>%t; FileCheck %s --check-prefixes=CHECK,CHECKM1 <%t
+
+declare void @ext(i32)
+
+define i32 @jt1(i32 %a, i32 %b) {
+entry:
+  switch i32 %a, label %return [
+    i32 1, label %bb1
+    i32 2, label %bb2
+    i32 3, label %bb3
+    i32 4, label %bb4
+    i32 5, label %bb5
+    i32 6, label %bb6
+    i32 7, label %bb7
+    i32 8, label %bb8
+    i32 9, label %bb9
+    i32 10, label %bb10
+    i32 11, label %bb11
+    i32 12, label %bb12
+    i32 13, label %bb13
+    i32 14, label %bb14
+    i32 15, label %bb15
+    i32 16, label %bb16
+    i32 17, label %bb17
+  ]
+; CHECK-LABEL: function jt1:
+; CHECK: Jump Tables:
+; CHECK0-NEXT: jt#0:
+; CHECK0-NOT: jt#1:
+; CHECK4-NEXT: jt#0:
+; CHECK4-SAME: jt#1:
+; CHECK4-SAME: jt#2:
+; CHECK4-SAME: jt#3:
+; CHECK4-NOT: jt#4:
+; CHECK8-NEXT: jt#0:
+; CHECK8-SAME: jt#1:
+; CHECK8-SAME: jt#2: BB#14 BB#15 BB#16 BB#17{{$}}
+; CHECK8-NOT: jt#3:
+; CHECKM1-NEXT: jt#0:
+; CHECKM1-SAME: jt#1: BB#13 BB#14 BB#15 BB#16 BB#17{{$}}
+; CHECKM1-NOT: jt#2:
+; CHEC-NEXT: Function Live Ins:
+
+bb1: tail call void @ext(i32 0) br label %return
+bb2: tail call void @ext(i32 2) br label %return
+bb3: tail call void @ext(i32 4) br label %return
+bb4: tail call void @ext(i32 6) br label %return
+bb5: tail call void @ext(i32 8) br label %return
+bb6: tail call void @ext(i32 10) br label %return
+bb7: tail call void @ext(i32 12) br label %return
+bb8: tail call void @ext(i32 14) br label %return
+bb9: tail call void @ext(i32 16) br label %return
+bb10: tail call void @ext(i32 18) br label %return
+bb11: tail call void @ext(i32 20) br label %return
+bb12: tail call void @ext(i32 22) br label %return
+bb13: tail call void @ext(i32 24) br label %return
+bb14: tail call void @ext(i32 26) br label %return
+bb15: tail call void @ext(i32 28) br label %return
+bb16: tail call void @ext(i32 30) br label %return
+bb17: tail call void @ext(i32 32) br label %return
+
+return: ret i32 %b
+}
+
+define void @jt2(i32 %x) {
+entry:
+  switch i32 %x, label %return [
+    i32 1, label %bb1
+    i32 2, label %bb2
+    i32 3, label %bb3
+    i32 4, label %bb4
+
+    i32 14, label %bb5
+    i32 15, label %bb6
+  ]
+; CHECK-LABEL: function jt2:
+; CHECK: Jump Tables:
+; CHECK0-NEXT: jt#0:  BB#1 BB#2 BB#3 BB#4 BB#7 BB#7 BB#7 BB#7 BB#7 BB#7 BB#7 BB#7 BB#7 BB#5 BB#6{{$}}
+; CHECK4-NEXT: jt#0:  BB#1 BB#2 BB#3 BB#4{{$}}
+; CHECK8-NEXT: jt#0:  BB#1 BB#2 BB#3 BB#4{{$}}
+; CHECKM1-NEXT: jt#0:  BB#1 BB#2 BB#3 BB#4{{$}}
+; CHEC-NEXT: Function Live Ins:
+
+bb1: tail call void @ext(i32 1) br label %return
+bb2: tail call void @ext(i32 2) br label %return
+bb3: tail call void @ext(i32 3) br label %return
+bb4: tail call void @ext(i32 4) br label %return
+bb5: tail call void @ext(i32 5) br label %return
+bb6: tail call void @ext(i32 6) br label %return
+return: ret void
+}