llvm/CodeGen/SwitchLoweringUtils.h

0001 //===- SwitchLoweringUtils.h - Switch Lowering ------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_CODEGEN_SWITCHLOWERINGUTILS_H
0010 #define LLVM_CODEGEN_SWITCHLOWERINGUTILS_H
0011
0012 #include "llvm/ADT/SmallVector.h"
0013 #include "llvm/CodeGen/ISDOpcodes.h"
0014 #include "llvm/CodeGen/SelectionDAGNodes.h"
0015 #include "llvm/IR/InstrTypes.h"
0016 #include "llvm/Support/BranchProbability.h"
0017 #include <vector>
0018
0019 namespace llvm {
0020
0021 class BlockFrequencyInfo;
0022 class ConstantInt;
0023 class FunctionLoweringInfo;
0024 class MachineBasicBlock;
0025 class ProfileSummaryInfo;
0026 class TargetLowering;
0027 class TargetMachine;
0028
0029 namespace SwitchCG {
0030
0031 enum CaseClusterKind {
0032   /// A cluster of adjacent case labels with the same destination, or just one
0033   /// case.
0034   CC_Range,
0035   /// A cluster of cases suitable for jump table lowering.
0036   CC_JumpTable,
0037   /// A cluster of cases suitable for bit test lowering.
0038   CC_BitTests
0039 };
0040
0041 /// A cluster of case labels.
0042 struct CaseCluster {
0043   CaseClusterKind Kind;
0044   const ConstantInt *Low, *High;
0045   union {
0046     MachineBasicBlock *MBB;
0047     unsigned JTCasesIndex;
0048     unsigned BTCasesIndex;
0049   };
0050   BranchProbability Prob;
0051
0052   static CaseCluster range(const ConstantInt *Low, const ConstantInt *High,
0053                            MachineBasicBlock *MBB, BranchProbability Prob) {
0054     CaseCluster C;
0055     C.Kind = CC_Range;
0056     C.Low = Low;
0057     C.High = High;
0058     C.MBB = MBB;
0059     C.Prob = Prob;
0060     return C;
0061   }
0062
0063   static CaseCluster jumpTable(const ConstantInt *Low, const ConstantInt *High,
0064                                unsigned JTCasesIndex, BranchProbability Prob) {
0065     CaseCluster C;
0066     C.Kind = CC_JumpTable;
0067     C.Low = Low;
0068     C.High = High;
0069     C.JTCasesIndex = JTCasesIndex;
0070     C.Prob = Prob;
0071     return C;
0072   }
0073
0074   static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High,
0075                               unsigned BTCasesIndex, BranchProbability Prob) {
0076     CaseCluster C;
0077     C.Kind = CC_BitTests;
0078     C.Low = Low;
0079     C.High = High;
0080     C.BTCasesIndex = BTCasesIndex;
0081     C.Prob = Prob;
0082     return C;
0083   }
0084 };
0085
0086 using CaseClusterVector = std::vector<CaseCluster>;
0087 using CaseClusterIt = CaseClusterVector::iterator;
0088
0089 /// Sort Clusters and merge adjacent cases.
0090 void sortAndRangeify(CaseClusterVector &Clusters);
0091
0092 struct CaseBits {
0093   uint64_t Mask = 0;
0094   MachineBasicBlock *BB = nullptr;
0095   unsigned Bits = 0;
0096   BranchProbability ExtraProb;
0097
0098   CaseBits() = default;
0099   CaseBits(uint64_t mask, MachineBasicBlock *bb, unsigned bits,
0100            BranchProbability Prob)
0101       : Mask(mask), BB(bb), Bits(bits), ExtraProb(Prob) {}
0102 };
0103
0104 using CaseBitsVector = std::vector<CaseBits>;
0105
0106 /// This structure is used to communicate between SelectionDAGBuilder and
0107 /// SDISel for the code generation of additional basic blocks needed by
0108 /// multi-case switch statements.
0109 struct CaseBlock {
0110   // For the GISel interface.
0111   struct PredInfoPair {
0112     CmpInst::Predicate Pred;
0113     // Set when no comparison should be emitted.
0114     bool NoCmp;
0115   };
0116   union {
0117     // The condition code to use for the case block's setcc node.
0118     // Besides the integer condition codes, this can also be SETTRUE, in which
0119     // case no comparison gets emitted.
0120     ISD::CondCode CC;
0121     struct PredInfoPair PredInfo;
0122   };
0123
0124   // The LHS/MHS/RHS of the comparison to emit.
0125   // Emit by default LHS op RHS. MHS is used for range comparisons:
0126   // If MHS is not null: (LHS <= MHS) and (MHS <= RHS).
0127   const Value *CmpLHS, *CmpMHS, *CmpRHS;
0128
0129   // The block to branch to if the setcc is true/false.
0130   MachineBasicBlock *TrueBB, *FalseBB;
0131
0132   // The block into which to emit the code for the setcc and branches.
0133   MachineBasicBlock *ThisBB;
0134
0135   /// The debug location of the instruction this CaseBlock was
0136   /// produced from.
0137   SDLoc DL;
0138   DebugLoc DbgLoc;
0139
0140   // Branch weights and predictability.
0141   BranchProbability TrueProb, FalseProb;
0142   bool IsUnpredictable;
0143
0144   // Constructor for SelectionDAG.
0145   CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs,
0146             const Value *cmpmiddle, MachineBasicBlock *truebb,
0147             MachineBasicBlock *falsebb, MachineBasicBlock *me, SDLoc dl,
0148             BranchProbability trueprob = BranchProbability::getUnknown(),
0149             BranchProbability falseprob = BranchProbability::getUnknown(),
0150             bool isunpredictable = false)
0151       : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
0152         TrueBB(truebb), FalseBB(falsebb), ThisBB(me), DL(dl),
0153         TrueProb(trueprob), FalseProb(falseprob),
0154         IsUnpredictable(isunpredictable) {}
0155
0156   // Constructor for GISel.
0157   CaseBlock(CmpInst::Predicate pred, bool nocmp, const Value *cmplhs,
0158             const Value *cmprhs, const Value *cmpmiddle,
0159             MachineBasicBlock *truebb, MachineBasicBlock *falsebb,
0160             MachineBasicBlock *me, DebugLoc dl,
0161             BranchProbability trueprob = BranchProbability::getUnknown(),
0162             BranchProbability falseprob = BranchProbability::getUnknown(),
0163             bool isunpredictable = false)
0164       : PredInfo({pred, nocmp}), CmpLHS(cmplhs), CmpMHS(cmpmiddle),
0165         CmpRHS(cmprhs), TrueBB(truebb), FalseBB(falsebb), ThisBB(me),
0166         DbgLoc(dl), TrueProb(trueprob), FalseProb(falseprob),
0167         IsUnpredictable(isunpredictable) {}
0168 };
0169
0170 struct JumpTable {
0171   /// The virtual register containing the index of the jump table entry
0172   /// to jump to.
0173   Register Reg;
0174   /// The JumpTableIndex for this jump table in the function.
0175   unsigned JTI;
0176   /// The MBB into which to emit the code for the indirect jump.
0177   MachineBasicBlock *MBB;
0178   /// The MBB of the default bb, which is a successor of the range
0179   /// check MBB.  This is when updating PHI nodes in successors.
0180   MachineBasicBlock *Default;
0181
0182   /// The debug location of the instruction this JumpTable was produced from.
0183   std::optional<SDLoc> SL; // For SelectionDAG
0184
0185   JumpTable(Register R, unsigned J, MachineBasicBlock *M, MachineBasicBlock *D,
0186             std::optional<SDLoc> SL)
0187       : Reg(R), JTI(J), MBB(M), Default(D), SL(SL) {}
0188 };
0189 struct JumpTableHeader {
0190   APInt First;
0191   APInt Last;
0192   const Value *SValue;
0193   MachineBasicBlock *HeaderBB;
0194   bool Emitted;
0195   bool FallthroughUnreachable = false;
0196
0197   JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H,
0198                   bool E = false)
0199       : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H),
0200         Emitted(E) {}
0201 };
0202 using JumpTableBlock = std::pair<JumpTableHeader, JumpTable>;
0203
0204 struct BitTestCase {
0205   uint64_t Mask;
0206   MachineBasicBlock *ThisBB;
0207   MachineBasicBlock *TargetBB;
0208   BranchProbability ExtraProb;
0209
0210   BitTestCase(uint64_t M, MachineBasicBlock *T, MachineBasicBlock *Tr,
0211               BranchProbability Prob)
0212       : Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) {}
0213 };
0214
0215 using BitTestInfo = SmallVector<BitTestCase, 3>;
0216
0217 struct BitTestBlock {
0218   APInt First;
0219   APInt Range;
0220   const Value *SValue;
0221   Register Reg;
0222   MVT RegVT;
0223   bool Emitted;
0224   bool ContiguousRange;
0225   MachineBasicBlock *Parent;
0226   MachineBasicBlock *Default;
0227   BitTestInfo Cases;
0228   BranchProbability Prob;
0229   BranchProbability DefaultProb;
0230   bool FallthroughUnreachable = false;
0231
0232   BitTestBlock(APInt F, APInt R, const Value *SV, Register Rg, MVT RgVT, bool E,
0233                bool CR, MachineBasicBlock *P, MachineBasicBlock *D,
0234                BitTestInfo C, BranchProbability Pr)
0235       : First(std::move(F)), Range(std::move(R)), SValue(SV), Reg(Rg),
0236         RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D),
0237         Cases(std::move(C)), Prob(Pr) {}
0238 };
0239
0240 /// Return the range of values within a range.
0241 uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First,
0242                            unsigned Last);
0243
0244 /// Return the number of cases within a range.
0245 uint64_t getJumpTableNumCases(const SmallVectorImpl<unsigned> &TotalCases,
0246                               unsigned First, unsigned Last);
0247
0248 struct SwitchWorkListItem {
0249   MachineBasicBlock *MBB = nullptr;
0250   CaseClusterIt FirstCluster;
0251   CaseClusterIt LastCluster;
0252   const ConstantInt *GE = nullptr;
0253   const ConstantInt *LT = nullptr;
0254   BranchProbability DefaultProb;
0255 };
0256 using SwitchWorkList = SmallVector<SwitchWorkListItem, 4>;
0257
0258 class SwitchLowering {
0259 public:
0260   SwitchLowering(FunctionLoweringInfo &funcinfo) : FuncInfo(funcinfo) {}
0261
0262   void init(const TargetLowering &tli, const TargetMachine &tm,
0263             const DataLayout &dl) {
0264     TLI = &tli;
0265     TM = &tm;
0266     DL = &dl;
0267   }
0268
0269   /// Vector of CaseBlock structures used to communicate SwitchInst code
0270   /// generation information.
0271   std::vector<CaseBlock> SwitchCases;
0272
0273   /// Vector of JumpTable structures used to communicate SwitchInst code
0274   /// generation information.
0275   std::vector<JumpTableBlock> JTCases;
0276
0277   /// Vector of BitTestBlock structures used to communicate SwitchInst code
0278   /// generation information.
0279   std::vector<BitTestBlock> BitTestCases;
0280
0281   void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
0282                       std::optional<SDLoc> SL, MachineBasicBlock *DefaultMBB,
0283                       ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI);
0284
0285   bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First,
0286                       unsigned Last, const SwitchInst *SI,
0287                       const std::optional<SDLoc> &SL,
0288                       MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
0289
0290   void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
0291
0292   /// Build a bit test cluster from Clusters[First..Last]. Returns false if it
0293   /// decides it's not a good idea.
0294   bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
0295                      const SwitchInst *SI, CaseCluster &BTCluster);
0296
0297   virtual void addSuccessorWithProb(
0298       MachineBasicBlock *Src, MachineBasicBlock *Dst,
0299       BranchProbability Prob = BranchProbability::getUnknown()) = 0;
0300
0301   /// Determine the rank by weight of CC in [First,Last]. If CC has more weight
0302   /// than each cluster in the range, its rank is 0.
0303   unsigned caseClusterRank(const CaseCluster &CC, CaseClusterIt First,
0304                            CaseClusterIt Last);
0305
0306   struct SplitWorkItemInfo {
0307     CaseClusterIt LastLeft;
0308     CaseClusterIt FirstRight;
0309     BranchProbability LeftProb;
0310     BranchProbability RightProb;
0311   };
0312   /// Compute information to balance the tree based on branch probabilities to
0313   /// create a near-optimal (in terms of search time given key frequency) binary
0314   /// search tree. See e.g. Kurt Mehlhorn "Nearly Optimal Binary Search Trees"
0315   /// (1975).
0316   SplitWorkItemInfo computeSplitWorkItemInfo(const SwitchWorkListItem &W);
0317   virtual ~SwitchLowering() = default;
0318
0319 private:
0320   const TargetLowering *TLI = nullptr;
0321   const TargetMachine *TM = nullptr;
0322   const DataLayout *DL = nullptr;
0323   FunctionLoweringInfo &FuncInfo;
0324 };
0325
0326 } // namespace SwitchCG
0327 } // namespace llvm
0328
0329 #endif // LLVM_CODEGEN_SWITCHLOWERINGUTILS_H