Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -5293,9 +5293,9 @@ for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) { ConstantInt *CaseVal = CI->getCaseValue(); - if (CaseVal->getValue().slt(MinCaseVal->getValue())) + if (CaseVal->getValue().ult(MinCaseVal->getValue())) MinCaseVal = CaseVal; - if (CaseVal->getValue().sgt(MaxCaseVal->getValue())) + if (CaseVal->getValue().ugt(MaxCaseVal->getValue())) MaxCaseVal = CaseVal; // Resulting value at phi nodes for this case value. @@ -5491,17 +5491,6 @@ return true; } -static bool isSwitchDense(ArrayRef 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. /// @@ -5513,58 +5502,112 @@ static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI) { + // The number of cases that need to be removed by a subtraction operation + // to make it worth using. + const unsigned SubThreshold = (SI->getFunction()->hasOptSize() ? 2 : 8); + bool MadeChanges = false; auto *CondTy = cast(SI->getCondition()->getType()); - if (CondTy->getIntegerBitWidth() > 64 || - !DL.fitsInLegalInteger(CondTy->getIntegerBitWidth())) + unsigned BitWidth = CondTy->getIntegerBitWidth(); + if (BitWidth > 64 || + !DL.fitsInLegalInteger(BitWidth)) return false; - // Only bother with this optimization if there are more than 3 switch cases; - // SDAG will only bother creating jump tables for 4 or more cases. - if (SI->getNumCases() < 4) + + // No point in optimizing less than 3 cases. + if (SI->getNumCases() < 3) return false; - // This transform is agnostic to the signedness of the input or case values. We - // can treat the case values as signed or unsigned. We can optimize more common - // cases such as a sequence crossing zero {-4,0,4,8} if we interpret case values - // as signed. - SmallVector Values; + SmallVector Values; for (auto &C : SI->cases()) - Values.push_back(C.getCaseValue()->getValue().getSExtValue()); + Values.push_back(C.getCaseValue()->getLimitedValue()); llvm::sort(Values); - // If the switch is already dense, there's nothing useful to do here. - if (isSwitchDense(Values)) - return false; + // A cheap speculative transform: handle power-of-two flags using + // @clz or @ctz as the key function. + // TODO: this transform would benifit from proper range analysis in SwitchToLookupTable + // BitWidth > 8 could be relaxed after this is fixed, but not eliminated, because + // this transforms 0 => BitWidth. + bool UseClz = false; + bool UseCtz = false; + if (BitWidth > 8 || + SI->getFunction()->hasOptSize()) { + unsigned MaxPopCount = 0; + unsigned MinClz = 64, MaxClz = 0, MinCtz = 64, MaxCtz = 0; + for (auto &V : Values) { + MaxPopCount = countPopulation(V); + if (MaxPopCount > 1) + break; + unsigned Clz = APInt(BitWidth, V).countLeadingZeros(); + unsigned Ctz = APInt(BitWidth, V).countTrailingZeros(); + if (Clz < MinClz) MinClz = Clz; + if (Clz > MaxClz) MaxClz = Clz; + if (Ctz < MinCtz) MinCtz = Ctz; + if (Ctz > MaxCtz) MaxCtz = Ctz; + } + // Without this check we might do clz followed by ctz, and if Values contains 0, + // the result might be woorse. + if (MaxPopCount == 1 && Values.back() > 64) { + MadeChanges = true; + // Prefer clz because it is one instruction cheaper + // on ARM, but they cost the same on x86 so if we only need + // the subtraction on clz use ctz. + UseClz = (MinClz < SubThreshold) || (MinCtz >= SubThreshold); + if (UseClz) + for (auto &V : Values) + V = APInt(BitWidth, V).countLeadingZeros(); + else { + UseCtz = true; + for (auto &V : Values) { + V = APInt(BitWidth, V).countTrailingZeros(); + } + } + // 0 will suddenly become the largest (BitWidth), so we need to sort again. + llvm::sort(Values); + } + } - // First, transform the values such that they start at zero and ascend. - int64_t Base = Values[0]; - for (auto &V : Values) - V -= (uint64_t)(Base); + // Find the element that has the most distance from it's previous, wrapping around. + uint64_t BestDistance = APInt::getMaxValue(CondTy->getIntegerBitWidth()).getLimitedValue() - + Values.back() + Values.front() + 1; + unsigned BestIndex = 0; + for (unsigned i = 1;i != Values.size();i++) { + if (Values[i] - Values[i-1] > BestDistance) { + BestIndex = i; + BestDistance = Values[i] - Values[i-1]; + } + } - // Now we have signed numbers that have been shifted so that, given enough - // precision, there are no negative values. Since the rest of the transform - // is bitwise only, we switch now to an unsigned representation. - uint64_t GCD = 0; - for (auto &V : Values) - GCD = GreatestCommonDivisor64(GCD, (uint64_t)V); + uint64_t Base = 0; + // Now transform the values such that they start at zero and ascend. + if ((BestDistance > SubThreshold) && + (BestIndex != 0 || (Values[0] >= SubThreshold))) { + Base = Values[BestIndex]; + MadeChanges = true; + for (auto &V : Values) + V = (APInt(BitWidth, V) - Base).getLimitedValue(); + } // This transform can be done speculatively because it is so cheap - it results - // in a single rotate operation being inserted. This can only happen if the - // factor extracted is a power of 2. - // FIXME: If the GCD is an odd number we can multiply by the multiplicative - // inverse of GCD and then perform this transform. - // FIXME: It's possible that optimizing a switch on powers of two might also - // be beneficial - flag values are often powers of two and we could use a CLZ - // as the key function. - if (GCD <= 1 || !isPowerOf2_64(GCD)) - // No common divisor found or too expensive to compute key function. - return false; - - unsigned Shift = Log2_64(GCD); - for (auto &V : Values) - V = (int64_t)((uint64_t)V >> Shift); + // in a single rotate operation being inserted. + unsigned Shift = 64; + for (auto &V : Values) { + // There is no edge condition when the BitWidth is less than 64, because there + // is at least 3 distinct cases. (LLVM requires well-formed IR to not have + // duplicate cases). + unsigned TZ = countTrailingZeros(V); + if (TZ < Shift) { + Shift = TZ; + if (Shift == 0) + break; + } + } + if (Shift) { + MadeChanges = true; + for (auto &V : Values) + V = V >> Shift; + } - if (!isSwitchDense(Values)) - // Transform didn't create a dense switch. + if (!MadeChanges) + // Didn't do anything return false; // The obvious transform is to shift the switch condition right and emit a @@ -5578,20 +5621,44 @@ // default case. auto *Ty = cast(SI->getCondition()->getType()); - Builder.SetInsertPoint(SI); - auto *ShiftC = ConstantInt::get(Ty, Shift); - auto *Sub = Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base)); - auto *LShr = Builder.CreateLShr(Sub, ShiftC); - auto *Shl = Builder.CreateShl(Sub, Ty->getBitWidth() - Shift); - auto *Rot = Builder.CreateOr(LShr, Shl); - SI->replaceUsesOfWith(SI->getCondition(), Rot); + { + auto Zero = ConstantInt::get(IntegerType::get(Ty->getContext(), 1), 0); + Builder.SetInsertPoint(SI); + Value *ZerosTransform; + if (UseClz) { + Function *Ctlz = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::ctlz, Ty); + ZerosTransform = Builder.Insert(CallInst::Create(Ctlz, {SI->getCondition(), Zero})); + } else if (UseCtz) { + Function *Cttz = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::cttz, Ty); + ZerosTransform = Builder.Insert(CallInst::Create(Cttz, {SI->getCondition(), Zero})); + } else + ZerosTransform = SI->getCondition(); + + auto *Sub = Builder.CreateSub(ZerosTransform, ConstantInt::get(Ty, Base)); + Value *Key; + if (Shift) { + Function *Fshr = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::fshr, Ty); + auto *ShiftC = ConstantInt::get(Ty, Shift); + Key = Builder.Insert(CallInst::Create(Fshr, {Sub, Sub, ShiftC})); + } else + Key = Sub; + SI->replaceUsesOfWith(SI->getCondition(), Key); + } for (auto Case : SI->cases()) { auto *Orig = Case.getCaseValue(); - auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base); + uint64_t Zeros; + if (UseClz) + Zeros = Orig->getValue().countLeadingZeros(); + else if (UseCtz) + Zeros = Orig->getValue().countTrailingZeros(); + else + Zeros = Orig->getValue().getLimitedValue(); + auto Sub = (APInt(BitWidth, Zeros) - Base).getLimitedValue(); Case.setValue( - cast(ConstantInt::get(Ty, Sub.lshr(ShiftC->getValue())))); + cast(ConstantInt::get(Ty, APInt(BitWidth, Sub >> Shift)))); } + return true; } @@ -5631,6 +5698,9 @@ if (Options.ForwardSwitchCondToPhi && ForwardSwitchConditionToPHI(SI)) return requestResimplify(); + if (ReduceSwitchRange(SI, Builder, DL, TTI)) + return requestResimplify(); + // The conversion from switch to lookup tables results in difficult-to-analyze // code and makes pruning branches much harder. This is a problem if the // switch expression itself can still be restricted as a result of inlining or @@ -5640,9 +5710,6 @@ SwitchToLookupTable(SI, Builder, DL, TTI)) return requestResimplify(); - if (ReduceSwitchRange(SI, Builder, DL, TTI)) - return requestResimplify(); - return false; } Index: test/Transforms/SimplifyCFG/switch-simplify-range.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/switch-simplify-range.ll @@ -0,0 +1,153 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -S -simplifycfg < %s | FileCheck %s +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define i64 @switch_common_right_bits(i8 %a) #0 { +; CHECK-LABEL: @switch_common_right_bits( +; CHECK-NEXT: Entry: +; CHECK-NEXT: [[TMP0:%.*]] = sub i8 [[A:%.*]], -3 +; CHECK-NEXT: [[TMP1:%.*]] = call i8 @llvm.fshr.i8(i8 [[TMP0]], i8 [[TMP0]], i8 1) +; CHECK-NEXT: switch i8 [[TMP1]], label [[SWITCHELSE:%.*]] [ +; CHECK-NEXT: i8 0, label [[SWITCHPRONG:%.*]] +; CHECK-NEXT: i8 1, label [[SWITCHPRONG1:%.*]] +; CHECK-NEXT: i8 2, label [[SWITCHPRONG2:%.*]] +; CHECK-NEXT: i8 3, label [[SWITCHPRONG3:%.*]] +; CHECK-NEXT: ] +; CHECK: SwitchElse: +; CHECK-NEXT: [[MERGE:%.*]] = phi i64 [ 10, [[ENTRY:%.*]] ], [ 6, [[SWITCHPRONG]] ], [ 3, [[SWITCHPRONG1]] ], [ 3, [[SWITCHPRONG2]] ], [ 3, [[SWITCHPRONG3]] ] +; CHECK-NEXT: ret i64 [[MERGE]] +; CHECK: SwitchProng: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng1: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng2: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng3: +; CHECK-NEXT: br label [[SWITCHELSE]] +; +Entry: + switch i8 %a, label %SwitchElse [ + i8 253, label %SwitchProng + i8 255, label %SwitchProng1 + i8 1, label %SwitchProng2 + i8 3, label %SwitchProng3 + ] +SwitchElse: ; preds = %Entry + ret i64 10 +SwitchProng: ; preds = %Entry + ret i64 6 +SwitchProng1: ; preds = %Entry + ret i64 3 +SwitchProng2: ; preds = %Entry + ret i64 3 +SwitchProng3: ; preds = %Entry + ret i64 3 +} + +define i64 @switch_ctz(i16 %a) optsize #0 { +; CHECK-LABEL: @switch_ctz( +; CHECK-NEXT: Entry: +; CHECK-NEXT: [[TMP0:%.*]] = call i16 @llvm.cttz.i16(i16 [[A:%.*]], i1 false) +; CHECK-NEXT: [[TMP1:%.*]] = sub i16 [[TMP0]], 0 +; CHECK-NEXT: switch i16 [[TMP1]], label [[SWITCHELSE:%.*]] [ +; CHECK-NEXT: i16 1, label [[SWITCHPRONG:%.*]] +; CHECK-NEXT: i16 2, label [[SWITCHPRONG1:%.*]] +; CHECK-NEXT: i16 3, label [[SWITCHPRONG2:%.*]] +; CHECK-NEXT: i16 0, label [[SWITCHPRONG3:%.*]] +; CHECK-NEXT: i16 6, label [[SWITCHPRONG6:%.*]] +; CHECK-NEXT: i16 7, label [[SWITCHPRONG7:%.*]] +; CHECK-NEXT: i16 4, label [[SWITCHPRONG5:%.*]] +; CHECK-NEXT: i16 5, label [[SWITCHPRONG4:%.*]] +; CHECK-NEXT: ] +; CHECK: SwitchElse: +; CHECK-NEXT: [[MERGE:%.*]] = phi i64 [ 10, [[ENTRY:%.*]] ], [ 6, [[SWITCHPRONG]] ], [ 3, [[SWITCHPRONG1]] ], [ 35, [[SWITCHPRONG2]] ], [ 31, [[SWITCHPRONG3]] ], [ 53, [[SWITCHPRONG4]] ], [ 51, [[SWITCHPRONG5]] ], [ 41, [[SWITCHPRONG6]] ], [ 34, [[SWITCHPRONG7]] ] +; CHECK-NEXT: ret i64 [[MERGE]] +; CHECK: SwitchProng: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng1: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng2: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng3: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng4: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng5: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng6: +; CHECK-NEXT: br label [[SWITCHELSE]] +; CHECK: SwitchProng7: +; CHECK-NEXT: br label [[SWITCHELSE]] +; +Entry: + switch i16 %a, label %SwitchElse [ + i16 2, label %SwitchProng + i16 4, label %SwitchProng1 + i16 8, label %SwitchProng2 + i16 1, label %SwitchProng3 + i16 64, label %SwitchProng6 + i16 128, label %SwitchProng7 + i16 16, label %SwitchProng5 + i16 32, label %SwitchProng4 + ] +SwitchElse: ; preds = %Entry + ret i64 10 +SwitchProng: ; preds = %Entry + ret i64 6 +SwitchProng1: ; preds = %Entry + ret i64 3 +SwitchProng2: ; preds = %Entry + ret i64 35 +SwitchProng3: ; preds = %Entry + ret i64 31 +SwitchProng4: ; preds = %Entry + ret i64 53 +SwitchProng5: ; preds = %Entry + ret i64 51 +SwitchProng6: ; preds = %Entry + ret i64 41 +SwitchProng7: ; preds = %Entry + ret i64 34 +} + +define i64 @switch_clz(i8 %a) optsize #0 { +; CHECK-LABEL: @switch_clz( +; CHECK-NEXT: Entry: +; CHECK-NEXT: [[TMP0:%.*]] = call i8 @llvm.ctlz.i8(i8 [[A:%.*]], i1 false) +; CHECK-NEXT: [[TMP1:%.*]] = sub i8 [[TMP0]], 0 +; CHECK-NEXT: switch i8 [[TMP1]], label [[SWITCHELSE:%.*]] [ +; CHECK-NEXT: i8 0, label [[SWITCHPRONG2:%.*]] +; CHECK-NEXT: i8 1, label [[SWITCHPRONG3:%.*]] +; CHECK-NEXT: i8 2, label [[SWITCHPRONG6:%.*]] +; CHECK-NEXT: i8 8, label [[SWITCHPRONG5:%.*]] +; CHECK-NEXT: ] +; CHECK: SwitchProng2: +; CHECK-NEXT: [[MERGE:%.*]] = phi i64 [ 35, [[ENTRY:%.*]] ], [ 31, [[SWITCHPRONG3]] ], [ 41, [[SWITCHPRONG6]] ], [ 40, [[SWITCHPRONG5]] ], [ 12, [[SWITCHELSE]] ] +; CHECK-NEXT: ret i64 [[MERGE]] +; CHECK: SwitchProng3: +; CHECK-NEXT: br label [[SWITCHPRONG2]] +; CHECK: SwitchProng6: +; CHECK-NEXT: br label [[SWITCHPRONG2]] +; CHECK: SwitchProng5: +; CHECK-NEXT: br label [[SWITCHPRONG2]] +; CHECK: SwitchElse: +; CHECK-NEXT: br label [[SWITCHPRONG2]] +; +Entry: + switch i8 %a, label %SwitchElse [ + i8 128, label %SwitchProng2 + i8 64, label %SwitchProng3 + i8 32, label %SwitchProng6 + i8 0, label %SwitchProng5 + ] +SwitchProng2: ; preds = %Entry + ret i64 35 +SwitchProng3: ; preds = %Entry + ret i64 31 +SwitchProng6: ; preds = %Entry + ret i64 41 +SwitchProng5: ; preds = %Entry + ret i64 40 +SwitchElse: ; preds = %Entry + ret i64 12 +}