Switch to Select range optimization

[kariddi]

Summary

This is a follow up for http://reviews.llvm.org/D5620 .

This optimization tries one step further trying to detect cases where we can use a pivot to distinguish between the two case groups.

At the moment if the optimization detects that a default target is present in the switch it bails out, but it tries to see if that default can trigger or not.

[hans]

The patch seems to have been uploaded without context. If you're uploading the patch manually (i.e. not using arcanist), please generate the diff with -U99999. That way it's much easier to look at it in the review tool.

lib/Transforms/Utils/SimplifyCFG.cpp

3540

I don't see any need for auto here..

for (ConstantInt *Case : Cases)

would be clearer, and it avoids making Case a reference to a pointer type, which seems unnecessary.

3721

Using known bits to figure out if the default case can trigger is clever. Other optimizations would benefit from this too, so I think SimplifyCFG should have a separate transformation that does this analysis and makes the default case unreachable. That way more optimizations benefit, and the code here becomes simpler.

[kariddi]

Ok, thanks Hans!
I will do it next time. I usually use "git diff" for generating the diff , I'll take a look at Arcanist too though.

lib/Transforms/Utils/SimplifyCFG.cpp

3540

Will do.

3721

Do you think I should hoist it to a separate static function in SimplifyCFG?

Is this what you had in mind?

lib/Transforms/Utils/SimplifyCFG.cpp

   return true;
 }
 
+// AnalyzeSwitchCases - Helper function to compute information about switch
+// cases, like the minimum and the maximum case.
+static void AnalyzeSwitchCases(const SmallVectorImpl<ConstantInt *> &Cases,
+                               const APInt &KnownZeroBitsCond,
+                               const APInt &KnownOneBitsCond,
+                               ConstantInt *&MinCase, ConstantInt *&MaxCase,
+                               unsigned &ValidCases) {
+  MinCase = Cases[0];
+  MaxCase = Cases[0];
+  // Compute the number of patterns covered by the cases of each result,
+  // the minimum and maximum cases and the zeroes and ones for this case group.
+  for (auto &Case : Cases) {
+    bool CaseMatchesCondPattern =
+        ((~Case->getValue() & KnownZeroBitsCond) == KnownZeroBitsCond) &&
+        ((Case->getValue() & KnownOneBitsCond) == KnownOneBitsCond);
+
+    // Increment the number of cases covered by
+    // the condition pattern in the group.
+    if (CaseMatchesCondPattern)
+      ++ValidCases;
+    // Compute the minimum and maximum case.
+    if (MinCase->getValue().sgt(Case->getValue()))
+      MinCase = Case;
+    if (MaxCase->getValue().slt(Case->getValue()))
+      MaxCase = Case;
+  }
+}
+
 // ConvertTwoCaseSwitch - Helper function that checks if it is possible to
 // transform a switch with only two cases (or two cases + default)
 // that produces a result into a value select.

   return nullptr;
 }
 
+// ConvertRangeSwitch - Helper function that checks if it is possible to
+// transform a switch with cases arranged into two ordered not overlapping
+// groups into a value select.
+//
+// Example:
+// switch (a) {
+//   case 0: case 2:
+//   case 4: case 6:
+//   case 8: case 10:
+//   case 12: case 14:
+//     return 10;         ---->   %0 = icmp ult i32 %a, 15
+//                                %1 = select i1 %0, i32 10, i32 20
+//   case 16: case 18:
+//   case 20: case 22:
+//   case 24: case 26:
+//   case 28: case 30:
+//     return 20;
+// }
+static Value *
+ConvertRangeSwitch(const SwitchCaseResultVectorTy &ResultVector,
+                   Value *Condition,
+                   bool DefaultCanTrigger, ConstantInt *MinCaseFirst,
+                   ConstantInt *MinCaseSecond, ConstantInt *MaxCaseFirst,
+                   ConstantInt *MaxCaseSecond, IRBuilder<> &Builder) {
+  const bool FirstIsBigger =
+    MinCaseFirst->getValue().sgt(MaxCaseSecond->getValue());
+  const bool SecondIsBigger =
+      MinCaseSecond->getValue().sgt(MaxCaseFirst->getValue());
+  // If the case statements ranges do not overlap use a comparison to
+  // distinguish between the two groups.
+  if (!DefaultCanTrigger && (FirstIsBigger || SecondIsBigger)) {
+    ConstantInt *Pivot = SecondIsBigger ? MaxCaseFirst : MaxCaseSecond;
+    Value *const SelectLHS =
+        SecondIsBigger ? ResultVector[0].first : ResultVector[1].first;
+    Value *const SelectRHS =
+        SecondIsBigger ? ResultVector[1].first : ResultVector[0].first;
+    Value *const ValueCompare =
+        Builder.CreateICmpSGT(Condition, Pivot, "switch.rangesub");
+    return Builder.CreateSelect(ValueCompare, SelectRHS, SelectLHS,
+                                "switch.rangeselect");
+  }
+
+  return nullptr;
+}
+
 // RemoveSwitchAfterSelectConversion - Helper function to cleanup a switch
 // instruction that has been converted into a select, fixing up PHI nodes and
 // basic blocks.

     return false;
   assert(PHI != nullptr && "PHI for value select not found");
 
+  const unsigned BitWidth = Cond->getType()->getIntegerBitWidth();
+
+  APInt KnownZerosCond(BitWidth, 0), KnownOnesCond(BitWidth, 0);
+  // Compute known bits of the Condition of the Switch statement.
+  computeKnownBits(Cond, KnownZerosCond, KnownOnesCond, DL, 0, AT, SI);
+  // Number of bits that are fixed in the switch condition value.
+  const unsigned NumKnownCondBits =
+      (KnownZerosCond | KnownOnesCond).countPopulation();
+
   Builder.SetInsertPoint(SI);
   Value *SelectValue = ConvertTwoCaseSwitch(
       UniqueResults,

     RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder);
     return true;
   }
+
+  // The switch has more than only two cases. Check to see if we can
+  // still transform it into a select
+  unsigned FirstGroupValidCases = 0, SecondGroupValidCases = 0;
+  ConstantInt *MinCaseFirst = nullptr, *MinCaseSecond = nullptr,
+              *MaxCaseFirst = nullptr, *MaxCaseSecond = nullptr;
+  // Analyze the Switch cases of the two groups, collecting the number of cases
+  // each groups covers (pessimistically) and which are the minimum and maximum
+  // case values for each group.
+  AnalyzeSwitchCases(UniqueResults[0].second, KnownZerosCond, KnownOnesCond,
+                     MinCaseFirst, MaxCaseFirst, FirstGroupValidCases);
+  AnalyzeSwitchCases(UniqueResults[1].second, KnownZerosCond, KnownOnesCond,
+                     MinCaseSecond, MaxCaseSecond, SecondGroupValidCases);
+  // The default case can trigger if a default value has been found and
+  // if there are some possible bit combination of the condition value
+  // that are not covered from the case labels
+  bool DefaultCanTrigger = (((1 << (BitWidth - NumKnownCondBits)) -
+                        (FirstGroupValidCases + SecondGroupValidCases)) != 0);
+  DefaultCanTrigger &= (bool)DefaultResult;
+  // Try to convert the switch to a comparison to a pivot value between the two
+  // groups of cases.
+  SelectValue = ConvertRangeSwitch(
+      UniqueResults, Cond, DefaultCanTrigger,
+      MinCaseFirst, MinCaseSecond,
+      MaxCaseFirst, MaxCaseSecond, Builder);
+  if (SelectValue) {
+    RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder);
+    return true;
+  }
   // The switch couldn't be converted into a select.
   return false;
 }

test/Transforms/SimplifyCFG/switch-to-select-range.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+; The default case here stops us to be able to optimize,
+; because the range has holes.
+define i32 @foo2_with_default(i32 %a) {
+; CHECK-LABEL: @foo2_with_default
+; CHECK-NOT: select
+entry:
+  switch i32 %a, label %sw.default [
+    i32 10, label %sw.bb
+    i32 11, label %sw.bb
+    i32 12, label %sw.bb
+    i32 13, label %sw.bb
+    i32 14, label %sw.bb
+    i32 15, label %sw.bb
+    i32 19, label %sw.bb1
+    i32 20, label %sw.bb1
+    i32 21, label %sw.bb1
+    i32 22, label %sw.bb1
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 30, %sw.default ], [ 20, %sw.bb1 ], [ 10, %sw.bb ]
+  ret i32 %retval.0
+}
+
+; The default case here is unreachable, we detect that and so we can
+; optimize to a select.
+define i32 @foo2_without_default(i32 %a) {
+; CHECK-LABEL: @foo2_without_default
+; CHECK: %switch.rangeselect = select i1 %switch.rangesub, i32 20, i32 10
+entry:
+  %shl = shl i32 %a, 1
+  %and = and i32 %shl, 30
+  switch i32 %and, label %sw.default [
+    i32 0, label %sw.bb
+    i32 2, label %sw.bb
+    i32 4, label %sw.bb
+    i32 6, label %sw.bb
+    i32 8, label %sw.bb
+    i32 10, label %sw.bb
+    i32 12, label %sw.bb
+    i32 14, label %sw.bb
+    i32 16, label %sw.bb1
+    i32 18, label %sw.bb1
+    i32 20, label %sw.bb1
+    i32 22, label %sw.bb1
+    i32 24, label %sw.bb1
+    i32 26, label %sw.bb1
+    i32 28, label %sw.bb1
+    i32 30, label %sw.bb1
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 30, %sw.default ], [ 20, %sw.bb1 ], [ 10, %sw.bb ]
+  ret i32 %retval.0
+}