-bool SelectionDAGBuilder::isDense(const CaseClusterVector &Clusters,
- unsigned *TotalCases, unsigned First,
- unsigned Last) {
- assert(Last >= First);
- assert(TotalCases[Last] >= TotalCases[First]);
-
- APInt LowCase = Clusters[First].Low->getValue();
- APInt HighCase = Clusters[Last].High->getValue();
- assert(LowCase.getBitWidth() == HighCase.getBitWidth());
-
- // FIXME: A range of consecutive cases has 100% density, but only requires one
- // comparison to lower. We should discriminate against such consecutive ranges
- // in jump tables.
-
- uint64_t Diff = (HighCase - LowCase).getLimitedValue((UINT64_MAX - 1) / 100);
- uint64_t Range = Diff + 1;
-
- uint64_t NumCases =
- TotalCases[Last] - (First == 0 ? 0 : TotalCases[First - 1]);
-
- assert(NumCases < UINT64_MAX / 100);
- assert(Range >= NumCases);
-
- return NumCases * 100 >= Range * MinJumpTableDensity;
-}
-
-static inline bool areJTsAllowed(const TargetLowering &TLI) {
- return TLI.isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
- TLI.isOperationLegalOrCustom(ISD::BRIND, MVT::Other);
-}
-
-bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters,
- unsigned First, unsigned Last,
- const SwitchInst *SI,
- MachineBasicBlock *DefaultMBB,
- CaseCluster &JTCluster) {
- assert(First <= Last);
-
- uint64_t Weight = 0;
- unsigned NumCmps = 0;
- std::vector<MachineBasicBlock*> Table;
- DenseMap<MachineBasicBlock*, uint32_t> JTWeights;
- for (unsigned I = First; I <= Last; ++I) {
- assert(Clusters[I].Kind == CC_Range);
- Weight += Clusters[I].Weight;
- APInt Low = Clusters[I].Low->getValue();
- APInt High = Clusters[I].High->getValue();
- NumCmps += (Low == High) ? 1 : 2;
- if (I != First) {
- // Fill the gap between this and the previous cluster.
- APInt PreviousHigh = Clusters[I - 1].High->getValue();
- assert(PreviousHigh.slt(Low));
- uint64_t Gap = (Low - PreviousHigh).getLimitedValue() - 1;
- for (uint64_t J = 0; J < Gap; J++)
- Table.push_back(DefaultMBB);
- }
- for (APInt X = Low; X.sle(High); ++X)
- Table.push_back(Clusters[I].MBB);
- JTWeights[Clusters[I].MBB] += Clusters[I].Weight;
- }
-
- unsigned NumDests = JTWeights.size();
- if (isSuitableForBitTests(NumDests, NumCmps,
- Clusters[First].Low->getValue(),
- Clusters[Last].High->getValue())) {
- // Clusters[First..Last] should be lowered as bit tests instead.
- return false;
- }
-
- // Create the MBB that will load from and jump through the table.
- // Note: We create it here, but it's not inserted into the function yet.
- MachineFunction *CurMF = FuncInfo.MF;
- MachineBasicBlock *JumpTableMBB =
- CurMF->CreateMachineBasicBlock(SI->getParent());
-
- // Add successors. Note: use table order for determinism.
- SmallPtrSet<MachineBasicBlock *, 8> Done;
- for (MachineBasicBlock *Succ : Table) {
- if (Done.count(Succ))
- continue;
- addSuccessorWithWeight(JumpTableMBB, Succ, JTWeights[Succ]);
- Done.insert(Succ);
- }
-
- const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- unsigned JTI = CurMF->getOrCreateJumpTableInfo(TLI.getJumpTableEncoding())
- ->createJumpTableIndex(Table);
-
- // Set up the jump table info.
- JumpTable JT(-1U, JTI, JumpTableMBB, nullptr);
- JumpTableHeader JTH(Clusters[First].Low->getValue(),
- Clusters[Last].High->getValue(), SI->getCondition(),
- nullptr, false);
- JTCases.push_back(JumpTableBlock(JTH, JT));
-
- JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High,
- JTCases.size() - 1, Weight);
- return true;
-}
-
-void SelectionDAGBuilder::findJumpTables(CaseClusterVector &Clusters,
- const SwitchInst *SI,
- MachineBasicBlock *DefaultMBB) {
-#ifndef NDEBUG
- // Clusters must be non-empty, sorted, and only contain Range clusters.
- assert(!Clusters.empty());
- for (CaseCluster &C : Clusters)
- assert(C.Kind == CC_Range);
- for (unsigned i = 1, e = Clusters.size(); i < e; ++i)
- assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue()));
-#endif
-
- const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- if (!areJTsAllowed(TLI))
- return;
-
- const int64_t N = Clusters.size();
- const unsigned MinJumpTableSize = TLI.getMinimumJumpTableEntries();
-
- // Split Clusters into minimum number of dense partitions. The algorithm uses
- // the same idea as Kannan & Proebsting "Correction to 'Producing Good Code
- // for the Case Statement'" (1994), but builds the MinPartitions array in
- // reverse order to make it easier to reconstruct the partitions in ascending
- // order. In the choice between two optimal partitionings, it picks the one
- // which yields more jump tables.
-
- // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1].
- SmallVector<unsigned, 8> MinPartitions(N);
- // LastElement[i] is the last element of the partition starting at i.
- SmallVector<unsigned, 8> LastElement(N);
- // NumTables[i]: nbr of >= MinJumpTableSize partitions from Clusters[i..N-1].
- SmallVector<unsigned, 8> NumTables(N);
- // TotalCases[i]: Total nbr of cases in Clusters[0..i].
- SmallVector<unsigned, 8> TotalCases(N);
-
- for (unsigned i = 0; i < N; ++i) {
- APInt Hi = Clusters[i].High->getValue();
- APInt Lo = Clusters[i].Low->getValue();
- TotalCases[i] = (Hi - Lo).getLimitedValue() + 1;
- if (i != 0)
- TotalCases[i] += TotalCases[i - 1];
- }
-
- // Base case: There is only one way to partition Clusters[N-1].
- MinPartitions[N - 1] = 1;
- LastElement[N - 1] = N - 1;
- assert(MinJumpTableSize > 1);
- NumTables[N - 1] = 0;
-
- // Note: loop indexes are signed to avoid underflow.
- for (int64_t i = N - 2; i >= 0; i--) {
- // Find optimal partitioning of Clusters[i..N-1].
- // Baseline: Put Clusters[i] into a partition on its own.
- MinPartitions[i] = MinPartitions[i + 1] + 1;
- LastElement[i] = i;
- NumTables[i] = NumTables[i + 1];
-
- // Search for a solution that results in fewer partitions.
- for (int64_t j = N - 1; j > i; j--) {
- // Try building a partition from Clusters[i..j].
- if (isDense(Clusters, &TotalCases[0], i, j)) {
- unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
- bool IsTable = j - i + 1 >= MinJumpTableSize;
- unsigned Tables = IsTable + (j == N - 1 ? 0 : NumTables[j + 1]);
-
- // If this j leads to fewer partitions, or same number of partitions
- // with more lookup tables, it is a better partitioning.
- if (NumPartitions < MinPartitions[i] ||
- (NumPartitions == MinPartitions[i] && Tables > NumTables[i])) {
- MinPartitions[i] = NumPartitions;
- LastElement[i] = j;
- NumTables[i] = Tables;
- }
- }
- }
- }
-
- // Iterate over the partitions, replacing some with jump tables in-place.
- unsigned DstIndex = 0;
- for (unsigned First = 0, Last; First < N; First = Last + 1) {
- Last = LastElement[First];
- assert(Last >= First);
- assert(DstIndex <= First);
- unsigned NumClusters = Last - First + 1;
-
- CaseCluster JTCluster;
- if (NumClusters >= MinJumpTableSize &&
- buildJumpTable(Clusters, First, Last, SI, DefaultMBB, JTCluster)) {
- Clusters[DstIndex++] = JTCluster;
- } else {
- for (unsigned I = First; I <= Last; ++I)
- std::memmove(&Clusters[DstIndex++], &Clusters[I], sizeof(Clusters[I]));
- }
- }
- Clusters.resize(DstIndex);
-}
-
-bool SelectionDAGBuilder::rangeFitsInWord(const APInt &Low, const APInt &High) {
- // FIXME: Using the pointer type doesn't seem ideal.
- uint64_t BW = DAG.getTargetLoweringInfo().getPointerTy().getSizeInBits();
- uint64_t Range = (High - Low).getLimitedValue(UINT64_MAX - 1) + 1;
- return Range <= BW;
-}
-
-bool SelectionDAGBuilder::isSuitableForBitTests(unsigned NumDests,
- unsigned NumCmps,
- const APInt &Low,
- const APInt &High) {
- // FIXME: I don't think NumCmps is the correct metric: a single case and a
- // range of cases both require only one branch to lower. Just looking at the
- // number of clusters and destinations should be enough to decide whether to
- // build bit tests.
-
- // To lower a range with bit tests, the range must fit the bitwidth of a
- // machine word.
- if (!rangeFitsInWord(Low, High))
- return false;
-
- // Decide whether it's profitable to lower this range with bit tests. Each
- // destination requires a bit test and branch, and there is an overall range
- // check branch. For a small number of clusters, separate comparisons might be
- // cheaper, and for many destinations, splitting the range might be better.
- return (NumDests == 1 && NumCmps >= 3) ||
- (NumDests == 2 && NumCmps >= 5) ||
- (NumDests == 3 && NumCmps >= 6);
-}
-
-bool SelectionDAGBuilder::buildBitTests(CaseClusterVector &Clusters,
- unsigned First, unsigned Last,
- const SwitchInst *SI,
- CaseCluster &BTCluster) {
- assert(First <= Last);
- if (First == Last)
- return false;
-
- BitVector Dests(FuncInfo.MF->getNumBlockIDs());
- unsigned NumCmps = 0;
- for (int64_t I = First; I <= Last; ++I) {
- assert(Clusters[I].Kind == CC_Range);
- Dests.set(Clusters[I].MBB->getNumber());
- NumCmps += (Clusters[I].Low == Clusters[I].High) ? 1 : 2;
- }
- unsigned NumDests = Dests.count();
-
- APInt Low = Clusters[First].Low->getValue();
- APInt High = Clusters[Last].High->getValue();
- assert(Low.slt(High));
-
- if (!isSuitableForBitTests(NumDests, NumCmps, Low, High))
- return false;
-
- APInt LowBound;
- APInt CmpRange;
-
- const int BitWidth =
- DAG.getTargetLoweringInfo().getPointerTy().getSizeInBits();
- assert((High - Low + 1).sle(BitWidth) && "Case range must fit in bit mask!");
-
- if (Low.isNonNegative() && High.slt(BitWidth)) {
- // Optimize the case where all the case values fit in a
- // word without having to subtract minValue. In this case,
- // we can optimize away the subtraction.
- LowBound = APInt::getNullValue(Low.getBitWidth());
- CmpRange = High;
- } else {
- LowBound = Low;
- CmpRange = High - Low;
- }
-
- CaseBitsVector CBV;
- uint64_t TotalWeight = 0;
- for (unsigned i = First; i <= Last; ++i) {
- // Find the CaseBits for this destination.
- unsigned j;
- for (j = 0; j < CBV.size(); ++j)
- if (CBV[j].BB == Clusters[i].MBB)
- break;
- if (j == CBV.size())
- CBV.push_back(CaseBits(0, Clusters[i].MBB, 0, 0));
- CaseBits *CB = &CBV[j];
-
- // Update Mask, Bits and ExtraWeight.
- uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue();
- uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue();
- for (uint64_t j = Lo; j <= Hi; ++j) {
- CB->Mask |= 1ULL << j;
- CB->Bits++;
- }
- CB->ExtraWeight += Clusters[i].Weight;
- TotalWeight += Clusters[i].Weight;
- }
-
- BitTestInfo BTI;
- std::sort(CBV.begin(), CBV.end(), [](const CaseBits &a, const CaseBits &b) {
- // FIXME: Sort by weight.
- return a.Bits > b.Bits;
- });
-
- for (auto &CB : CBV) {
- MachineBasicBlock *BitTestBB =
- FuncInfo.MF->CreateMachineBasicBlock(SI->getParent());
- BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraWeight));
- }
- BitTestCases.push_back(BitTestBlock(LowBound, CmpRange, SI->getCondition(),
- -1U, MVT::Other, false, nullptr,
- nullptr, std::move(BTI)));
-
- BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High,
- BitTestCases.size() - 1, TotalWeight);
- return true;
-}
-
-void SelectionDAGBuilder::findBitTestClusters(CaseClusterVector &Clusters,
- const SwitchInst *SI) {
-// Partition Clusters into as few subsets as possible, where each subset has a
-// range that fits in a machine word and has <= 3 unique destinations.
-
-#ifndef NDEBUG
- // Clusters must be sorted and contain Range or JumpTable clusters.
- assert(!Clusters.empty());
- assert(Clusters[0].Kind == CC_Range || Clusters[0].Kind == CC_JumpTable);
- for (const CaseCluster &C : Clusters)
- assert(C.Kind == CC_Range || C.Kind == CC_JumpTable);
- for (unsigned i = 1; i < Clusters.size(); ++i)
- assert(Clusters[i-1].High->getValue().slt(Clusters[i].Low->getValue()));
-#endif
-
- // If target does not have legal shift left, do not emit bit tests at all.
- const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- EVT PTy = TLI.getPointerTy();
- if (!TLI.isOperationLegal(ISD::SHL, PTy))
- return;
-
- int BitWidth = PTy.getSizeInBits();
- const int64_t N = Clusters.size();
-
- // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1].
- SmallVector<unsigned, 8> MinPartitions(N);
- // LastElement[i] is the last element of the partition starting at i.
- SmallVector<unsigned, 8> LastElement(N);
-
- // FIXME: This might not be the best algorithm for finding bit test clusters.
-
- // Base case: There is only one way to partition Clusters[N-1].
- MinPartitions[N - 1] = 1;
- LastElement[N - 1] = N - 1;
-
- // Note: loop indexes are signed to avoid underflow.
- for (int64_t i = N - 2; i >= 0; --i) {
- // Find optimal partitioning of Clusters[i..N-1].
- // Baseline: Put Clusters[i] into a partition on its own.
- MinPartitions[i] = MinPartitions[i + 1] + 1;
- LastElement[i] = i;
-
- // Search for a solution that results in fewer partitions.
- // Note: the search is limited by BitWidth, reducing time complexity.
- for (int64_t j = std::min(N - 1, i + BitWidth - 1); j > i; --j) {
- // Try building a partition from Clusters[i..j].
-
- // Check the range.
- if (!rangeFitsInWord(Clusters[i].Low->getValue(),
- Clusters[j].High->getValue()))
- continue;
-
- // Check nbr of destinations and cluster types.
- // FIXME: This works, but doesn't seem very efficient.
- bool RangesOnly = true;
- BitVector Dests(FuncInfo.MF->getNumBlockIDs());
- for (int64_t k = i; k <= j; k++) {
- if (Clusters[k].Kind != CC_Range) {
- RangesOnly = false;
- break;
- }
- Dests.set(Clusters[k].MBB->getNumber());
- }
- if (!RangesOnly || Dests.count() > 3)
- break;
-
- // Check if it's a better partition.
- unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
- if (NumPartitions < MinPartitions[i]) {
- // Found a better partition.
- MinPartitions[i] = NumPartitions;
- LastElement[i] = j;
- }
- }
- }
-
- // Iterate over the partitions, replacing with bit-test clusters in-place.
- unsigned DstIndex = 0;
- for (unsigned First = 0, Last; First < N; First = Last + 1) {
- Last = LastElement[First];
- assert(First <= Last);
- assert(DstIndex <= First);
-
- CaseCluster BitTestCluster;
- if (buildBitTests(Clusters, First, Last, SI, BitTestCluster)) {
- Clusters[DstIndex++] = BitTestCluster;
- } else {
- for (unsigned I = First; I <= Last; ++I)
- std::memmove(&Clusters[DstIndex++], &Clusters[I], sizeof(Clusters[I]));
- }
- }
- Clusters.resize(DstIndex);
-}
-
-void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond,
- MachineBasicBlock *SwitchMBB,
- MachineBasicBlock *DefaultMBB) {
- MachineFunction *CurMF = FuncInfo.MF;
- MachineBasicBlock *NextMBB = nullptr;
- MachineFunction::iterator BBI = W.MBB;
- if (++BBI != FuncInfo.MF->end())
- NextMBB = BBI;
-
- unsigned Size = W.LastCluster - W.FirstCluster + 1;
-
- BranchProbabilityInfo *BPI = FuncInfo.BPI;
-
- if (Size == 2 && W.MBB == SwitchMBB) {
- // If any two of the cases has the same destination, and if one value
- // is the same as the other, but has one bit unset that the other has set,
- // use bit manipulation to do two compares at once. For example:
- // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)"
- // TODO: This could be extended to merge any 2 cases in switches with 3
- // cases.
- // TODO: Handle cases where W.CaseBB != SwitchBB.
- CaseCluster &Small = *W.FirstCluster;
- CaseCluster &Big = *W.LastCluster;
-
- if (Small.Low == Small.High && Big.Low == Big.High &&
- Small.MBB == Big.MBB) {
- const APInt &SmallValue = Small.Low->getValue();
- const APInt &BigValue = Big.Low->getValue();
-
- // Check that there is only one bit different.
- if (BigValue.countPopulation() == SmallValue.countPopulation() + 1 &&
- (SmallValue | BigValue) == BigValue) {
- // Isolate the common bit.
- APInt CommonBit = BigValue & ~SmallValue;
- assert((SmallValue | CommonBit) == BigValue &&
- CommonBit.countPopulation() == 1 && "Not a common bit?");
-
- SDValue CondLHS = getValue(Cond);
- EVT VT = CondLHS.getValueType();
- SDLoc DL = getCurSDLoc();
-
- SDValue Or = DAG.getNode(ISD::OR, DL, VT, CondLHS,
- DAG.getConstant(CommonBit, VT));
- SDValue Cond = DAG.getSetCC(DL, MVT::i1, Or,
- DAG.getConstant(BigValue, VT), ISD::SETEQ);
-
- // Update successor info.
- // Both Small and Big will jump to Small.BB, so we sum up the weights.
- addSuccessorWithWeight(SwitchMBB, Small.MBB, Small.Weight + Big.Weight);
- addSuccessorWithWeight(
- SwitchMBB, DefaultMBB,
- // The default destination is the first successor in IR.
- BPI ? BPI->getEdgeWeight(SwitchMBB->getBasicBlock(), (unsigned)0)
- : 0);
-
- // Insert the true branch.
- SDValue BrCond =
- DAG.getNode(ISD::BRCOND, DL, MVT::Other, getControlRoot(), Cond,
- DAG.getBasicBlock(Small.MBB));
- // Insert the false branch.
- BrCond = DAG.getNode(ISD::BR, DL, MVT::Other, BrCond,
- DAG.getBasicBlock(DefaultMBB));
-
- DAG.setRoot(BrCond);
- return;
- }
- }
- }
-
- if (TM.getOptLevel() != CodeGenOpt::None) {
- // Order cases by weight so the most likely case will be checked first.
- std::sort(W.FirstCluster, W.LastCluster + 1,
- [](const CaseCluster &a, const CaseCluster &b) {
- return a.Weight > b.Weight;
- });
-
- // Rearrange the case blocks so that the last one falls through if possible.
- // Start at the bottom as that's the case with the lowest weight.
- // FIXME: Take branch probability into account.
- for (CaseClusterIt I = W.LastCluster - 1; I >= W.FirstCluster; --I) {
- if (I->Kind == CC_Range && I->MBB == NextMBB) {
- std::swap(*I, *W.LastCluster);
- break;
- }
- }
- }
-
- // Compute total weight.
- uint32_t UnhandledWeights = 0;
- for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I)
- UnhandledWeights += I->Weight;
-
- MachineBasicBlock *CurMBB = W.MBB;
- for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) {
- MachineBasicBlock *Fallthrough;
- if (I == W.LastCluster) {
- // For the last cluster, fall through to the default destination.
- Fallthrough = DefaultMBB;
- } else {
- Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock());
- CurMF->insert(BBI, Fallthrough);
- // Put Cond in a virtual register to make it available from the new blocks.
- ExportFromCurrentBlock(Cond);
- }
-
- switch (I->Kind) {
- case CC_JumpTable: {
- // FIXME: Optimize away range check based on pivot comparisons.
- JumpTableHeader *JTH = &JTCases[I->JTCasesIndex].first;
- JumpTable *JT = &JTCases[I->JTCasesIndex].second;
-
- // The jump block hasn't been inserted yet; insert it here.
- MachineBasicBlock *JumpMBB = JT->MBB;
- CurMF->insert(BBI, JumpMBB);
- addSuccessorWithWeight(CurMBB, Fallthrough);
- addSuccessorWithWeight(CurMBB, JumpMBB);
-
- // The jump table header will be inserted in our current block, do the
- // range check, and fall through to our fallthrough block.
- JTH->HeaderBB = CurMBB;
- JT->Default = Fallthrough; // FIXME: Move Default to JumpTableHeader.
-
- // If we're in the right place, emit the jump table header right now.
- if (CurMBB == SwitchMBB) {
- visitJumpTableHeader(*JT, *JTH, SwitchMBB);
- JTH->Emitted = true;
- }
- break;
- }
- case CC_BitTests: {
- // FIXME: Optimize away range check based on pivot comparisons.
- BitTestBlock *BTB = &BitTestCases[I->BTCasesIndex];
-
- // The bit test blocks haven't been inserted yet; insert them here.
- for (BitTestCase &BTC : BTB->Cases)
- CurMF->insert(BBI, BTC.ThisBB);
-
- // Fill in fields of the BitTestBlock.
- BTB->Parent = CurMBB;
- BTB->Default = Fallthrough;
-
- // If we're in the right place, emit the bit test header header right now.
- if (CurMBB ==SwitchMBB) {
- visitBitTestHeader(*BTB, SwitchMBB);
- BTB->Emitted = true;
- }
- break;
- }
- case CC_Range: {
- const Value *RHS, *LHS, *MHS;
- ISD::CondCode CC;
- if (I->Low == I->High) {
- // Check Cond == I->Low.
- CC = ISD::SETEQ;
- LHS = Cond;
- RHS=I->Low;
- MHS = nullptr;
- } else {
- // Check I->Low <= Cond <= I->High.
- CC = ISD::SETLE;
- LHS = I->Low;
- MHS = Cond;
- RHS = I->High;
- }
-
- // The false weight is the sum of all unhandled cases.
- UnhandledWeights -= I->Weight;
- CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Weight,
- UnhandledWeights);
-
- if (CurMBB == SwitchMBB)
- visitSwitchCase(CB, SwitchMBB);
- else
- SwitchCases.push_back(CB);
-
- break;
- }
- }
- CurMBB = Fallthrough;
- }
-}
-
-void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList,
- const SwitchWorkListItem &W,
- Value *Cond,
- MachineBasicBlock *SwitchMBB) {
- assert(W.FirstCluster->Low->getValue().slt(W.LastCluster->Low->getValue()) &&
- "Clusters not sorted?");
-
- unsigned NumClusters = W.LastCluster - W.FirstCluster + 1;
- assert(NumClusters >= 2 && "Too small to split!");
-
- // FIXME: When we have profile info, we might want to balance the tree based
- // on weights instead of node count.
-
- CaseClusterIt PivotCluster = W.FirstCluster + NumClusters / 2;
- CaseClusterIt FirstLeft = W.FirstCluster;
- CaseClusterIt LastLeft = PivotCluster - 1;
- CaseClusterIt FirstRight = PivotCluster;
- CaseClusterIt LastRight = W.LastCluster;
- const ConstantInt *Pivot = PivotCluster->Low;
-
- // New blocks will be inserted immediately after the current one.
- MachineFunction::iterator BBI = W.MBB;
- ++BBI;
-
- // We will branch to the LHS if Value < Pivot. If LHS is a single cluster,
- // we can branch to its destination directly if it's squeezed exactly in
- // between the known lower bound and Pivot - 1.
- MachineBasicBlock *LeftMBB;
- if (FirstLeft == LastLeft && FirstLeft->Kind == CC_Range &&
- FirstLeft->Low == W.GE &&
- (FirstLeft->High->getValue() + 1LL) == Pivot->getValue()) {
- LeftMBB = FirstLeft->MBB;
- } else {
- LeftMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock());
- FuncInfo.MF->insert(BBI, LeftMBB);
- WorkList.push_back({LeftMBB, FirstLeft, LastLeft, W.GE, Pivot});
- // Put Cond in a virtual register to make it available from the new blocks.
- ExportFromCurrentBlock(Cond);
- }
-
- // Similarly, we will branch to the RHS if Value >= Pivot. If RHS is a
- // single cluster, RHS.Low == Pivot, and we can branch to its destination
- // directly if RHS.High equals the current upper bound.
- MachineBasicBlock *RightMBB;
- if (FirstRight == LastRight && FirstRight->Kind == CC_Range &&
- W.LT && (FirstRight->High->getValue() + 1ULL) == W.LT->getValue()) {
- RightMBB = FirstRight->MBB;
- } else {
- RightMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock());
- FuncInfo.MF->insert(BBI, RightMBB);
- WorkList.push_back({RightMBB, FirstRight, LastRight, Pivot, W.LT});
- // Put Cond in a virtual register to make it available from the new blocks.
- ExportFromCurrentBlock(Cond);
- }
-
- // Create the CaseBlock record that will be used to lower the branch.
- CaseBlock CB(ISD::SETLT, Cond, Pivot, nullptr, LeftMBB, RightMBB, W.MBB);
-
- if (W.MBB == SwitchMBB)
- visitSwitchCase(CB, SwitchMBB);
- else
- SwitchCases.push_back(CB);
-}
-
-void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) {
- // Extract cases from the switch.
- BranchProbabilityInfo *BPI = FuncInfo.BPI;
- CaseClusterVector Clusters;
- Clusters.reserve(SI.getNumCases());
- for (auto I : SI.cases()) {
- MachineBasicBlock *Succ = FuncInfo.MBBMap[I.getCaseSuccessor()];
- const ConstantInt *CaseVal = I.getCaseValue();
- uint32_t Weight = 0; // FIXME: Use 1 instead?
- if (BPI)
- Weight = BPI->getEdgeWeight(SI.getParent(), I.getSuccessorIndex());
- Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Weight));
- }
-
- MachineBasicBlock *DefaultMBB = FuncInfo.MBBMap[SI.getDefaultDest()];
-
- if (TM.getOptLevel() != CodeGenOpt::None) {
- // Cluster adjacent cases with the same destination.
- sortAndRangeify(Clusters);
-
- // Replace an unreachable default with the most popular destination.
- // FIXME: Exploit unreachable default more aggressively.
- bool UnreachableDefault =
- isa<UnreachableInst>(SI.getDefaultDest()->getFirstNonPHIOrDbg());
- if (UnreachableDefault && !Clusters.empty()) {
- DenseMap<const BasicBlock *, unsigned> Popularity;
- unsigned MaxPop = 0;
- const BasicBlock *MaxBB = nullptr;
- for (auto I : SI.cases()) {
- const BasicBlock *BB = I.getCaseSuccessor();
- if (++Popularity[BB] > MaxPop) {
- MaxPop = Popularity[BB];
- MaxBB = BB;
- }
- }
- // Set new default.
- assert(MaxPop > 0 && MaxBB);
- DefaultMBB = FuncInfo.MBBMap[MaxBB];
-
- // Remove cases that were pointing to the destination that is now the
- // default.
- CaseClusterVector New;
- New.reserve(Clusters.size());
- for (CaseCluster &CC : Clusters) {
- if (CC.MBB != DefaultMBB)
- New.push_back(CC);
- }
- Clusters = std::move(New);
- }
- }
-
- // If there is only the default destination, jump there directly.
- MachineBasicBlock *SwitchMBB = FuncInfo.MBB;
- if (Clusters.empty()) {
- SwitchMBB->addSuccessor(DefaultMBB);
- if (DefaultMBB != NextBlock(SwitchMBB)) {
- DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other,
- getControlRoot(), DAG.getBasicBlock(SwitchMBB)));
- }
- return;
- }
-
- if (TM.getOptLevel() != CodeGenOpt::None) {
- findJumpTables(Clusters, &SI, DefaultMBB);
- findBitTestClusters(Clusters, &SI);
- }
-
-
- DEBUG({
- dbgs() << "Case clusters: ";
- for (const CaseCluster &C : Clusters) {
- if (C.Kind == CC_JumpTable) dbgs() << "JT:";
- if (C.Kind == CC_BitTests) dbgs() << "BT:";
-
- C.Low->getValue().print(dbgs(), true);
- if (C.Low != C.High) {
- dbgs() << '-';
- C.High->getValue().print(dbgs(), true);
- }
- dbgs() << ' ';
- }
- dbgs() << '\n';
- });
-
- assert(!Clusters.empty());
- SwitchWorkList WorkList;
- CaseClusterIt First = Clusters.begin();
- CaseClusterIt Last = Clusters.end() - 1;
- WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr});
-
- while (!WorkList.empty()) {
- SwitchWorkListItem W = WorkList.back();
- WorkList.pop_back();
- unsigned NumClusters = W.LastCluster - W.FirstCluster + 1;
-
- if (NumClusters > 3 && TM.getOptLevel() != CodeGenOpt::None) {
- // For optimized builds, lower large range as a balanced binary tree.
- splitWorkItem(WorkList, W, SI.getCondition(), SwitchMBB);
- continue;
- }
-
- lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB);
- }
-}
projects / oota-llvm.git / commitdiff