Lines Matching +full:low +full:- +full:to +full:- +full:high
1 //===- SwitchLoweringUtils.cpp - Switch Lowering --------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
26 const APInt &LowCase = Clusters[First].Low->getValue(); in getJumpTableRange()
27 const APInt &HighCase = Clusters[Last].High->getValue(); in getJumpTableRange()
31 // comparison to lower. We should discriminate against such consecutive ranges in getJumpTableRange()
33 return (HighCase - LowCase).getLimitedValue((UINT64_MAX - 1) / 100) + 1; in getJumpTableRange()
42 TotalCases[Last] - (First == 0 ? 0 : TotalCases[First - 1]); in getJumpTableNumCases()
53 // Clusters must be non-empty, sorted, and only contain Range clusters. in findJumpTables()
58 assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue())); in findJumpTables()
62 if (!TLI->areJTsAllowed(SI->getParent()->getParent())) in findJumpTables()
65 const unsigned MinJumpTableEntries = TLI->getMinimumJumpTableEntries(); in findJumpTables()
73 // Accumulated number of cases in each cluster and those prior to it. in findJumpTables()
76 const APInt &Hi = Clusters[i].High->getValue(); in findJumpTables()
77 const APInt &Lo = Clusters[i].Low->getValue(); in findJumpTables()
78 TotalCases[i] = (Hi - Lo).getLimitedValue() + 1; in findJumpTables()
80 TotalCases[i] += TotalCases[i - 1]; in findJumpTables()
83 uint64_t Range = getJumpTableRange(Clusters,0, N - 1); in findJumpTables()
84 uint64_t NumCases = getJumpTableNumCases(TotalCases, 0, N - 1); in findJumpTables()
89 if (TLI->isSuitableForJumpTable(SI, NumCases, Range, PSI, BFI)) { in findJumpTables()
91 if (buildJumpTable(Clusters, 0, N - 1, SI, SL, DefaultMBB, JTCluster)) { in findJumpTables()
98 // The algorithm below is not suitable for -O0. in findJumpTables()
99 if (TM->getOptLevel() == CodeGenOptLevel::None) in findJumpTables()
103 // the same idea as Kannan & Proebsting "Correction to 'Producing Good Code in findJumpTables()
105 // reverse order to make it easier to reconstruct the partitions in ascending in findJumpTables()
110 // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1]. in findJumpTables()
114 // PartitionsScore[i] is used to break ties when choosing between two in findJumpTables()
127 // Base case: There is only one way to partition Clusters[N-1]. in findJumpTables()
128 MinPartitions[N - 1] = 1; in findJumpTables()
129 LastElement[N - 1] = N - 1; in findJumpTables()
130 PartitionsScore[N - 1] = PartitionScores::SingleCase; in findJumpTables()
132 // Note: loop indexes are signed to avoid underflow. in findJumpTables()
133 for (int64_t i = N - 2; i >= 0; i--) { in findJumpTables()
134 // Find optimal partitioning of Clusters[i..N-1]. in findJumpTables()
141 for (int64_t j = N - 1; j > i; j--) { in findJumpTables()
148 if (TLI->isSuitableForJumpTable(SI, NumCases, Range, PSI, BFI)) { in findJumpTables()
149 unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]); in findJumpTables()
150 unsigned Score = j == N - 1 ? 0 : PartitionsScore[j + 1]; in findJumpTables()
151 int64_t NumEntries = j - i + 1; in findJumpTables()
160 // If this leads to fewer partitions, or to the same number of in findJumpTables()
172 // Iterate over the partitions, replacing some with jump tables in-place. in findJumpTables()
178 unsigned NumClusters = Last - First + 1; in findJumpTables()
212 const APInt &Low = Clusters[I].Low->getValue(); in buildJumpTable() local
213 const APInt &High = Clusters[I].High->getValue(); in buildJumpTable() local
214 NumCmps += (Low == High) ? 1 : 2; in buildJumpTable()
217 const APInt &PreviousHigh = Clusters[I - 1].High->getValue(); in buildJumpTable()
218 assert(PreviousHigh.slt(Low)); in buildJumpTable()
219 uint64_t Gap = (Low - PreviousHigh).getLimitedValue() - 1; in buildJumpTable()
223 uint64_t ClusterSize = (High - Low).getLimitedValue() + 1; in buildJumpTable()
230 if (TLI->isSuitableForBitTests(NumDests, NumCmps, in buildJumpTable()
231 Clusters[First].Low->getValue(), in buildJumpTable()
232 Clusters[Last].High->getValue(), *DL)) { in buildJumpTable()
241 CurMF->CreateMachineBasicBlock(SI->getParent()); in buildJumpTable()
251 JumpTableMBB->normalizeSuccProbs(); in buildJumpTable()
253 unsigned JTI = CurMF->getOrCreateJumpTableInfo(TLI->getJumpTableEncoding()) in buildJumpTable()
254 ->createJumpTableIndex(Table); in buildJumpTable()
257 JumpTable JT(-1U, JTI, JumpTableMBB, nullptr, SL); in buildJumpTable()
258 JumpTableHeader JTH(Clusters[First].Low->getValue(), in buildJumpTable()
259 Clusters[Last].High->getValue(), SI->getCondition(), in buildJumpTable()
263 JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High, in buildJumpTable()
264 JTCases.size() - 1, Prob); in buildJumpTable()
280 assert(Clusters[i-1].High->getValue().slt(Clusters[i].Low->getValue())); in findBitTestClusters()
283 // The algorithm below is not suitable for -O0. in findBitTestClusters()
284 if (TM->getOptLevel() == CodeGenOptLevel::None) in findBitTestClusters()
288 EVT PTy = TLI->getPointerTy(*DL); in findBitTestClusters()
289 if (!TLI->isOperationLegal(ISD::SHL, PTy)) in findBitTestClusters()
295 // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1]. in findBitTestClusters()
302 // Base case: There is only one way to partition Clusters[N-1]. in findBitTestClusters()
303 MinPartitions[N - 1] = 1; in findBitTestClusters()
304 LastElement[N - 1] = N - 1; in findBitTestClusters()
306 // Note: loop indexes are signed to avoid underflow. in findBitTestClusters()
307 for (int64_t i = N - 2; i >= 0; --i) { in findBitTestClusters()
308 // Find optimal partitioning of Clusters[i..N-1]. in findBitTestClusters()
315 for (int64_t j = std::min(N - 1, i + BitWidth - 1); j > i; --j) { in findBitTestClusters()
319 if (!TLI->rangeFitsInWord(Clusters[i].Low->getValue(), in findBitTestClusters()
320 Clusters[j].High->getValue(), *DL)) in findBitTestClusters()
326 BitVector Dests(FuncInfo.MF->getNumBlockIDs()); in findBitTestClusters()
332 Dests.set(Clusters[k].MBB->getNumber()); in findBitTestClusters()
338 unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]); in findBitTestClusters()
347 // Iterate over the partitions, replacing with bit-test clusters in-place. in findBitTestClusters()
358 size_t NumClusters = Last - First + 1; in findBitTestClusters()
375 BitVector Dests(FuncInfo.MF->getNumBlockIDs()); in buildBitTests()
379 Dests.set(Clusters[I].MBB->getNumber()); in buildBitTests()
380 NumCmps += (Clusters[I].Low == Clusters[I].High) ? 1 : 2; in buildBitTests()
384 APInt Low = Clusters[First].Low->getValue(); in buildBitTests() local
385 APInt High = Clusters[Last].High->getValue(); in buildBitTests() local
386 assert(Low.slt(High)); in buildBitTests()
388 if (!TLI->isSuitableForBitTests(NumDests, NumCmps, Low, High, *DL)) in buildBitTests()
394 const int BitWidth = TLI->getPointerTy(*DL).getSizeInBits(); in buildBitTests()
395 assert(TLI->rangeFitsInWord(Low, High, *DL) && in buildBitTests()
399 // range will jump to the default statement. in buildBitTests()
402 if (Clusters[I].Low->getValue() != Clusters[I - 1].High->getValue() + 1) { in buildBitTests()
408 if (Low.isStrictlyPositive() && High.slt(BitWidth)) { in buildBitTests()
410 // to subtract minValue. In this case, we can optimize away the subtraction. in buildBitTests()
411 LowBound = APInt::getZero(Low.getBitWidth()); in buildBitTests()
412 CmpRange = High; in buildBitTests()
415 LowBound = Low; in buildBitTests()
416 CmpRange = High - Low; in buildBitTests()
433 uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue(); in buildBitTests()
434 uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue(); in buildBitTests()
436 CB->Mask |= (-1ULL >> (63 - (Hi - Lo))) << Lo; in buildBitTests()
437 CB->Bits += Hi - Lo + 1; in buildBitTests()
438 CB->ExtraProb += Clusters[i].Prob; in buildBitTests()
454 FuncInfo.MF->CreateMachineBasicBlock(SI->getParent()); in buildBitTests()
458 SI->getCondition(), -1U, MVT::Other, false, in buildBitTests()
462 BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High, in buildBitTests()
463 BitTestCases.size() - 1, TotalProb); in buildBitTests()
470 assert(CC.Low == CC.High && "Input clusters must be single-case"); in sortAndRangeify()
474 return a.Low->getValue().slt(b.Low->getValue()); in sortAndRangeify()
482 const ConstantInt *CaseVal = CC.Low; in sortAndRangeify()
485 if (DstIndex != 0 && Clusters[DstIndex - 1].MBB == Succ && in sortAndRangeify()
486 (CaseVal->getValue() - Clusters[DstIndex - 1].High->getValue()) == 1) { in sortAndRangeify()
489 Clusters[DstIndex - 1].High = CaseVal; in sortAndRangeify()
490 Clusters[DstIndex - 1].Prob += CC.Prob; in sortAndRangeify()
507 return X.Low->getValue().slt(CC.Low->getValue()); in caseClusterRank()
516 auto LeftProb = LastLeft->Prob + W.DefaultProb / 2; in computeSplitWorkItemInfo()
517 auto RightProb = FirstRight->Prob + W.DefaultProb / 2; in computeSplitWorkItemInfo()
519 // Move LastLeft and FirstRight towards each other from opposite directions to in computeSplitWorkItemInfo()
522 // taken to ensure 0-probability nodes are distributed evenly. in computeSplitWorkItemInfo()
526 LeftProb += (++LastLeft)->Prob; in computeSplitWorkItemInfo()
528 RightProb += (--FirstRight)->Prob; in computeSplitWorkItemInfo()
534 // up to three values in each leaf. The pivot selection above doesn't take in computeSplitWorkItemInfo()
538 unsigned NumLeft = LastLeft - W.FirstCluster + 1; in computeSplitWorkItemInfo()
539 unsigned NumRight = W.LastCluster - FirstRight + 1; in computeSplitWorkItemInfo()
546 // Consider moving the first cluster on the right to the left side. in computeSplitWorkItemInfo()
551 // Moving the cluster to the left does not demote it. in computeSplitWorkItemInfo()
558 // Consider moving the last element on the left to the right side. in computeSplitWorkItemInfo()
563 // Moving the cluster to the right does not demot it. in computeSplitWorkItemInfo()
564 --LastLeft; in computeSplitWorkItemInfo()
565 --FirstRight; in computeSplitWorkItemInfo()