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