Index: include/llvm/IR/Instructions.h =================================================================== --- include/llvm/IR/Instructions.h +++ include/llvm/IR/Instructions.h @@ -3818,6 +3818,16 @@ static bool classof(const Value *V) { return isa(V) && classof(cast(V)); } + + // Implementation of Switch Value optimizations. Currently only the Maximum + // Value of the Switch Expression is recorded if it can be analyzed from the + // Instruction passed to the Switch parser. +private: + int MaxSwitchValue; + +public: + void setMaxSwitchValue(int Val) { MaxSwitchValue = Val; } + int getMaxSwitchValue() const { return MaxSwitchValue; } }; template <> Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -370,12 +370,14 @@ /// Lower W. void lowerWorkItem(SwitchWorkListItem W, Value *Cond, MachineBasicBlock *SwitchMBB, - MachineBasicBlock *DefaultMBB); + MachineBasicBlock *DefaultMBB, + bool omitDefaultBranch = false); /// Peel the top probability case if it exceeds the threshold MachineBasicBlock *peelDominantCaseCluster(const SwitchInst &SI, CaseClusterVector &Clusters, - BranchProbability &PeeledCaseProb); + BranchProbability &PeeledCaseProb, + bool omitDefaultBranch); /// A class which encapsulates all of the information needed to generate a /// stack protector check and signals to isel via its state being initialized @@ -847,7 +849,8 @@ MachineBasicBlock *SwitchBB); void visitJumpTable(JumpTable &JT); void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH, - MachineBasicBlock *SwitchBB); + MachineBasicBlock *SwitchBB, + bool omitDefaultBranch = false); private: // These all get lowered before this pass. Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2148,7 +2148,8 @@ /// in the JumpTable from switch case. void SelectionDAGBuilder::visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH, - MachineBasicBlock *SwitchBB) { + MachineBasicBlock *SwitchBB, + bool omitDefaultBranch) { SDLoc dl = getCurSDLoc(); // Subtract the lowest switch case value from the value being switched on and @@ -2173,24 +2174,30 @@ JumpTableReg, SwitchOp); JT.Reg = JumpTableReg; - // Emit the range check for the jump table, and branch to the default block - // for the switch statement if the value being switched on exceeds the largest - // case in the switch. - SDValue CMP = DAG.getSetCC( - dl, TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), - Sub.getValueType()), - Sub, DAG.getConstant(JTH.Last - JTH.First, dl, VT), ISD::SETUGT); - - SDValue BrCond = DAG.getNode(ISD::BRCOND, dl, - MVT::Other, CopyTo, CMP, - DAG.getBasicBlock(JT.Default)); - - // Avoid emitting unnecessary branches to the next block. - if (JT.MBB != NextBlock(SwitchBB)) - BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond, - DAG.getBasicBlock(JT.MBB)); - - DAG.setRoot(BrCond); + if (!omitDefaultBranch) { + // Emit the range check for the jump table, and branch to the default block + // for the switch statement if the value being switched on exceeds the largest + // case in the switch. + SDValue CMP = DAG.getSetCC( + dl, TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), + Sub.getValueType()), + Sub, DAG.getConstant(JTH.Last - JTH.First, dl, VT), ISD::SETUGT); + + SDValue BrCond = DAG.getNode(ISD::BRCOND, dl, + MVT::Other, CopyTo, CMP, + DAG.getBasicBlock(JT.Default)); + + // Avoid emitting unnecessary branches to the next block. + if (JT.MBB != NextBlock(SwitchBB)) + BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond, + DAG.getBasicBlock(JT.MBB)); + + DAG.setRoot(BrCond); + } else { + SDValue BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, CopyTo, + DAG.getBasicBlock(JT.MBB)); + DAG.setRoot(BrCond); + } } /// Create a LOAD_STACK_GUARD node, and let it carry the target specific global @@ -9796,7 +9803,8 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, MachineBasicBlock *SwitchMBB, - MachineBasicBlock *DefaultMBB) { + MachineBasicBlock *DefaultMBB, + bool omitDefaultBranch) { MachineFunction *CurMF = FuncInfo.MF; MachineBasicBlock *NextMBB = nullptr; MachineFunction::iterator BBI(W.MBB); @@ -9946,7 +9954,7 @@ // If we're in the right place, emit the jump table header right now. if (CurMBB == SwitchMBB) { - visitJumpTableHeader(*JT, *JTH, SwitchMBB); + visitJumpTableHeader(*JT, *JTH, SwitchMBB, omitDefaultBranch); JTH->Emitted = true; } break; @@ -10178,8 +10186,9 @@ // case. PeeledCaseProb is the BranchProbability for the peeled case. MachineBasicBlock *SelectionDAGBuilder::peelDominantCaseCluster( const SwitchInst &SI, CaseClusterVector &Clusters, - BranchProbability &PeeledCaseProb) { + BranchProbability &PeeledCaseProb, bool omitDefaultBranch) { MachineBasicBlock *SwitchMBB = FuncInfo.MBB; + // Don't perform if there is only one cluster or optimizing for size. if (SwitchPeelThreshold > 100 || !FuncInfo.BPI || Clusters.size() < 2 || TM.getOptLevel() == CodeGenOpt::None || @@ -10214,7 +10223,8 @@ auto PeeledCaseIt = Clusters.begin() + PeeledCaseIndex; SwitchWorkListItem W = {SwitchMBB, PeeledCaseIt, PeeledCaseIt, nullptr, nullptr, TopCaseProb.getCompl()}; - lowerWorkItem(W, SI.getCondition(), SwitchMBB, PeeledSwitchMBB); + lowerWorkItem(W, SI.getCondition(), SwitchMBB, PeeledSwitchMBB, + omitDefaultBranch); Clusters.erase(PeeledCaseIt); for (CaseCluster &CC : Clusters) { @@ -10232,7 +10242,21 @@ // Extract cases from the switch. BranchProbabilityInfo *BPI = FuncInfo.BPI; CaseClusterVector Clusters; - Clusters.reserve(SI.getNumCases()); + bool omitDefaultBranch = false; + + // If we have only the default case, then we need not generate the default + // jump table entries. Also, 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 (SI.getMaxSwitchValue() > (signed)SI.getNumCases() && + SI.getNumCases() > 0 && + (double)SI.getNumCases() / (double)SI.getMaxSwitchValue() > 0.70) + omitDefaultBranch = true; + + if (omitDefaultBranch) + Clusters.reserve(SI.getNumCases() + 1); + else + Clusters.reserve(SI.getNumCases()); for (auto I : SI.cases()) { MachineBasicBlock *Succ = FuncInfo.MBBMap[I.getCaseSuccessor()]; const ConstantInt *CaseVal = I.getCaseValue(); @@ -10249,7 +10273,23 @@ // if there are many clusters. sortAndRangeify(Clusters); - if (TM.getOptLevel() != CodeGenOpt::None) { + if (omitDefaultBranch && + Clusters[Clusters.size() - 1].High->getValue().slt(SI.getMaxSwitchValue())) { + const ConstantInt *Begin = + llvm::ConstantInt::get(*Context, + Clusters[Clusters.size() - 1].High->getValue() + 1); + const ConstantInt *End = llvm::ConstantInt::get(*Context, + APInt(Clusters[Clusters.size() - 1].High->getBitWidth(), + SI.getMaxSwitchValue())); + BranchProbability Prob = BranchProbability(1, SI.getMaxSwitchValue() + 1); + Clusters.push_back(CaseCluster::range(Begin, End, DefaultMBB, Prob)); + } else { + // The complete decision was only possible after the case statements were + // sorted in sortAndRageify(). Hence, make amends now. + omitDefaultBranch = false; + } + + if (TM.getOptLevel() != CodeGenOpt::None && ! omitDefaultBranch) { // Replace an unreachable default with the most popular destination. // FIXME: Exploit unreachable default more aggressively. bool UnreachableDefault = @@ -10284,7 +10324,7 @@ // The branch probablity of the peeled case. BranchProbability PeeledCaseProb = BranchProbability::getZero(); MachineBasicBlock *PeeledSwitchMBB = - peelDominantCaseCluster(SI, Clusters, PeeledCaseProb); + peelDominantCaseCluster(SI, Clusters, PeeledCaseProb, omitDefaultBranch); // If there is only the default destination, jump there directly. MachineBasicBlock *SwitchMBB = FuncInfo.MBB; @@ -10344,6 +10384,7 @@ continue; } - lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB); + lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB, + omitDefaultBranch); } } Index: lib/IR/Instructions.cpp =================================================================== --- lib/IR/Instructions.cpp +++ lib/IR/Instructions.cpp @@ -3506,6 +3506,7 @@ void SwitchInst::init(Value *Value, BasicBlock *Default, unsigned NumReserved) { assert(Value && Default && NumReserved); ReservedSpace = NumReserved; + MaxSwitchValue = 0; setNumHungOffUseOperands(2); allocHungoffUses(ReservedSpace); @@ -3546,6 +3547,7 @@ OL[i+1] = InOL[i+1]; } SubclassOptionalData = SI.SubclassOptionalData; + MaxSwitchValue = SI.getMaxSwitchValue(); } Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -5602,6 +5602,26 @@ return simplifyCFG(BB, TTI, Options) || true; } + // Analyze the switch expression and compute the highest possible value + // Analyze the switch expression to cull out information + // needed for switch optimizations. Currently we only analyze the maximum + // possible value of the expression and if known then rework the jump tables + // appropriately. + { + const DataLayout &DL = SI->getParent()->getParent()->getParent()->getDataLayout(); + 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). + if (Known.isNonNegative() && + (Known.countMinLeadingZeros() + Known.countMaxTrailingOnes()) == + valueWidth) + SI->setMaxSwitchValue((1 << Known.countMaxTrailingOnes()) - 1); + } + // Try to transform the switch into an icmp and a branch. if (TurnSwitchRangeIntoICmp(SI, Builder)) return simplifyCFG(BB, TTI, Options) || true;