[SimplifyCFG] Share code to compute switch density between ShouldBuildLookupTable() and ReduceSwitchRange()

[hans]

Summary

They're computing the same thing. No functionality change.

[thakis]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6119

Before we could handle table size up to UINT64_MAX / 10, after only up to UINT64_MAX / 100. That's not "no functionality change", is it?

[hans]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6119

I think it's still NFC in practice; we'd return false for table sizes of that magnitude anyway.

[thakis]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6119

Should we just remove all the overflow checks then?

[hans]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6119

No, you can still trigger overflows here, and overflowing would cause us to return the wrong answer.

For example:

switch (x) {
case 0: foo();
case VERY_BIG_NUMBER: bar();
}

TableSize will be VERY_BIG_NUMBER + 1, so overflowing when multiplying with 10 or 100 is a real concern.

But in practice, for huge table sizes, we'd return false later anyway, since it's not practically possible to have enough cases that the switch would be considered dense enough.

[thakis]

Makes sense, thanks!

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI,
   // TODO: We could relax this to any integer that fits in a register and rely
   // on ABI alignment and padding in the table to allow the load to be widened.
   // Or we could widen the constants and truncate the load.
   unsigned BitWidth = IT->getBitWidth();
   return BitWidth >= 8 && isPowerOf2_32(BitWidth) &&
          DL.fitsInLegalInteger(IT->getBitWidth());
 }
 
+static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange) {
+  // 40% is the default density for building a jump table in optsize/minsize
+  // mode. See also TargetLoweringBase::isSuitableForJumpTable(), which this
+  // function was based on.
+  const uint64_t MinDensity = 40;
+
+  if (CaseRange >= UINT64_MAX / 100)
+    return false; // Avoid multiplication overflows below.
+
+  return NumCases * 100 >= CaseRange * MinDensity;
+}
+
+static bool isSwitchDense(ArrayRef<int64_t> Values) {
+  uint64_t Diff = (uint64_t)Values.back() - (uint64_t)Values.front();
+  uint64_t Range = Diff + 1;
+  if (Range < Diff)
+    return false; // Overflow.
+
+  return isSwitchDense(Values.size(), Range);
+}
+
 /// Determine whether a lookup table should be built for this switch, based on
 /// the number of cases, size of the table, and the types of the results.
 // TODO: We could support larger than legal types by limiting based on the
 // number of loads required and/or table size. If the constants are small we
 // could use smaller table entries and extend after the load.
 static bool
 ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
                        const TargetTransformInfo &TTI, const DataLayout &DL,
                        const SmallDenseMap<PHINode *, Type *> &ResultTypes) {
-  if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10)
-    return false; // TableSize overflowed, or mul below might overflow.
+  if (SI->getNumCases() > TableSize)
+    return false; // TableSize overflowed.
 
   bool AllTablesFitInRegister = true;
   bool HasIllegalType = false;
   for (const auto &I : ResultTypes) {
     Type *Ty = I.second;
 
     // Saturate this flag to true.
     HasIllegalType = HasIllegalType || !isTypeLegalForLookupTable(Ty, TTI, DL);
ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
   // If each table would fit in a register, we should build it anyway.
   if (AllTablesFitInRegister)
     return true;
 
   // Don't build a table that doesn't fit in-register if it has illegal types.
   if (HasIllegalType)
     return false;
 
-  // The table density should be at least 40%. This is the same criterion as for
-  // jump tables, see SelectionDAGBuilder::handleJTSwitchCase.
-  // FIXME: Find the best cut-off.
-  return SI->getNumCases() * 10 >= TableSize * 4;
+  return isSwitchDense(SI->getNumCases(), TableSize);
 }
 
 /// Try to reuse the switch table index compare. Following pattern:
 /// \code
 ///     if (idx < tablesize)
 ///        r = table[idx]; // table does not contain default_value
 ///     else
 ///        r = default_value;
if (DTU)
     DTU->applyUpdates(Updates);
 
   ++NumLookupTables;
   if (NeedMask)
     ++NumLookupTablesHoles;
   return true;
 }
 
-static bool isSwitchDense(ArrayRef<int64_t> Values) {
-  // See also SelectionDAGBuilder::isDense(), which this function was based on.
-  uint64_t Diff = (uint64_t)Values.back() - (uint64_t)Values.front();
-  uint64_t Range = Diff + 1;
-  uint64_t NumCases = Values.size();
-  // 40% is the default density for building a jump table in optsize/minsize mode.
-  uint64_t MinDensity = 40;
-
-  return NumCases * 100 >= Range * MinDensity;
-}
-
 /// Try to transform a switch that has "holes" in it to a contiguous sequence
 /// of cases.
 ///
 /// A switch such as: switch(i) {case 5: case 9: case 13: case 17:} can be
 /// range-reduced to: switch ((i-5) / 4) {case 0: case 1: case 2: case 3:}.
 ///
 /// This converts a sparse switch into a dense switch which allows better
 /// lowering and could also allow transforming into a lookup table.