Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -4837,6 +4837,93 @@ SI->eraseFromParent(); } +// Analyze the switch expression and compute the highest possible value of the +// expression and if known then remap the known default values into individual +// case statements and direct them to the default block. Then mark the default +// destination as unreachable. +static bool convertFiniteDefaultValuesToCases(SwitchInst *SI, + const DataLayout &DL, + const TargetTransformInfo &TTI) { + unsigned ValueWidth = DL.getTypeSizeInBits(SI->getOperand(0)->getType()); + KnownBits Known(ValueWidth); + llvm::computeKnownBits(SI->getOperand(0), Known, DL); + + // We only care for non-negative values. The number of minimum leading + // zeros plus the number of maximum trailing ones should be equal to the + // width of the value. In that case, we say that the maximum switch value + // is equal to ((1 << number of maximum trailing ones) - 1). + APInt MaxSwitchValue(ValueWidth, 0); + APInt NumCases(ValueWidth, SI->getNumCases()); + if (Known.isNonNegative() && + (Known.countMinLeadingZeros() + Known.countMaxTrailingOnes()) == + ValueWidth) + MaxSwitchValue = (~Known.Zero); + + bool UnreachableDefault = + isa(SI->getDefaultDest()->getFirstNonPHIOrDbg()); + + // At least 70% of the possible values must be defined as case statements + // so that there is no penalty for those which have few defined case + // statements. + if (MaxSwitchValue.ugt(NumCases) && + SI->getNumCases() > 0 && !UnreachableDefault && + NumCases.roundToDouble() / MaxSwitchValue.roundToDouble() > 0.70) { + // Here we care for only those values that are beyond the highest case + // value and up to the MaxSwitchValue. The other missing values (holes) + // get automatically filled up during lowering. + BasicBlock *DefaultBlock = SI->getDefaultDest(); + SmallDenseMap DefaultResults; + SmallVector PHIs; + + // Resulting value at phi nodes for this case value. + SmallVector, 4> DefaultResultsList; + BasicBlock *CommonDest = nullptr; + if (DefaultBlock->phis().end() != DefaultBlock->phis().begin() && + ! GetCaseResults(SI, nullptr, DefaultBlock, &CommonDest, + DefaultResultsList, DL, TTI)) + return false; + + for (const auto &I : DefaultResultsList) { + PHINode *PHI = I.first; + Constant *Result = I.second; + DefaultResults[PHI] = Result; + PHIs.push_back(PHI); + } + + assert(SI->case_begin() != SI->case_end()); + SwitchInst::CaseIt CI = SI->case_begin(); + ConstantInt *MaxCaseVal = CI->getCaseValue(); + + for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) + if (CI->getCaseValue()->getValue().sgt(MaxCaseVal->getValue())) + MaxCaseVal = CI->getCaseValue(); + + for (int i = MaxCaseVal->getSExtValue() + 1; MaxSwitchValue.uge(i); i++) { + const APInt Val(ValueWidth, i, true); + const APInt ValUnsigned(ValueWidth, i); + SI->addCase(ConstantInt::get(DefaultBlock->getContext(), Val), + DefaultBlock); + if (MaxSwitchValue.ne(ValUnsigned)) { + for (PHINode *PHI : PHIs) { + PHI->addIncoming(DefaultResults[PHI], SI->getParent()); + } + } + } + + BasicBlock *NewDefaultBlock; + NewDefaultBlock = BasicBlock::Create(DefaultBlock->getContext(), + "switch.unreachable.default", + DefaultBlock->getParent()); + UnreachableInst *dummyInst LLVM_ATTRIBUTE_UNUSED; + dummyInst = new UnreachableInst(NewDefaultBlock->getContext(), + NewDefaultBlock); + SI->setDefaultDest(NewDefaultBlock); + return true; + } + + return false; +} + /// If the switch is only used to initialize one or more /// phi nodes in a common successor block with only two different /// constant values, replace the switch with select. @@ -5609,6 +5696,11 @@ return simplifyCFG(BB, TTI, Options) || true; } + // Try to convert small number of default values to individual case + // statements pointing to the default block. + if (convertFiniteDefaultValuesToCases(SI, DL, TTI)) + return simplifyCFG(BB, TTI, Options) || true; + // Try to transform the switch into an icmp and a branch. if (TurnSwitchRangeIntoICmp(SI, Builder)) return simplifyCFG(BB, TTI, Options) || true;