Lines Matching defs:Clusters
23 uint64_t SwitchCG::getJumpTableRange(const CaseClusterVector &Clusters,
26 const APInt &LowCase = Clusters[First].Low->getValue();
27 const APInt &HighCase = Clusters[Last].High->getValue();
46 void SwitchCG::SwitchLowering::findJumpTables(CaseClusterVector &Clusters,
53 // Clusters must be non-empty, sorted, and only contain Range clusters.
54 assert(!Clusters.empty());
55 for (CaseCluster &C : Clusters)
57 for (unsigned i = 1, e = Clusters.size(); i < e; ++i)
58 assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue()));
69 const int64_t N = Clusters.size();
76 const APInt &Hi = Clusters[i].High->getValue();
77 const APInt &Lo = Clusters[i].Low->getValue();
83 uint64_t Range = getJumpTableRange(Clusters,0, N - 1);
91 if (buildJumpTable(Clusters, 0, N - 1, SI, SL, DefaultMBB, JTCluster)) {
92 Clusters[0] = JTCluster;
93 Clusters.resize(1);
102 // Split Clusters into minimum number of dense partitions. The algorithm uses
110 // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1].
127 // Base case: There is only one way to partition Clusters[N-1].
134 // Find optimal partitioning of Clusters[i..N-1].
135 // Baseline: Put Clusters[i] into a partition on its own.
142 // Try building a partition from Clusters[i..j].
143 Range = getJumpTableRange(Clusters, i, j);
182 buildJumpTable(Clusters, First, Last, SI, SL, DefaultMBB, JTCluster)) {
183 Clusters[DstIndex++] = JTCluster;
186 std::memmove(&Clusters[DstIndex++], &Clusters[I], sizeof(Clusters[I]));
189 Clusters.resize(DstIndex);
192 bool SwitchCG::SwitchLowering::buildJumpTable(const CaseClusterVector &Clusters,
207 JTProbs[Clusters[I].MBB] = BranchProbability::getZero();
210 assert(Clusters[I].Kind == CC_Range);
211 Prob += Clusters[I].Prob;
212 const APInt &Low = Clusters[I].Low->getValue();
213 const APInt &High = Clusters[I].High->getValue();
217 const APInt &PreviousHigh = Clusters[I - 1].High->getValue();
225 Table.push_back(Clusters[I].MBB);
226 JTProbs[Clusters[I].MBB] += Clusters[I].Prob;
231 Clusters[First].Low->getValue(),
232 Clusters[Last].High->getValue(), *DL)) {
233 // Clusters[First..Last] should be lowered as bit tests instead.
258 JumpTableHeader JTH(Clusters[First].Low->getValue(),
259 Clusters[Last].High->getValue(), SI->getCondition(),
263 JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High,
268 void SwitchCG::SwitchLowering::findBitTestClusters(CaseClusterVector &Clusters,
270 // Partition Clusters into as few subsets as possible, where each subset has a
274 // Clusters must be sorted and contain Range or JumpTable clusters.
275 assert(!Clusters.empty());
276 assert(Clusters[0].Kind == CC_Range || Clusters[0].Kind == CC_JumpTable);
277 for (const CaseCluster &C : Clusters)
279 for (unsigned i = 1; i < Clusters.size(); ++i)
280 assert(Clusters[i-1].High->getValue().slt(Clusters[i].Low->getValue()));
293 const int64_t N = Clusters.size();
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].
308 // Find optimal partitioning of Clusters[i..N-1].
309 // Baseline: Put Clusters[i] into a partition on its own.
316 // Try building a partition from Clusters[i..j].
319 if (!TLI->rangeFitsInWord(Clusters[i].Low->getValue(),
320 Clusters[j].High->getValue(), *DL))
328 if (Clusters[k].Kind != CC_Range) {
332 Dests.set(Clusters[k].MBB->getNumber());
355 if (buildBitTests(Clusters, First, Last, SI, BitTestCluster)) {
356 Clusters[DstIndex++] = BitTestCluster;
359 std::memmove(&Clusters[DstIndex], &Clusters[First],
360 sizeof(Clusters[0]) * NumClusters);
364 Clusters.resize(DstIndex);
367 bool SwitchCG::SwitchLowering::buildBitTests(CaseClusterVector &Clusters,
378 assert(Clusters[I].Kind == CC_Range);
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();
402 if (Clusters[I].Low->getValue() != Clusters[I - 1].High->getValue() + 1) {
425 if (CBV[j].BB == Clusters[i].MBB)
429 CaseBits(0, Clusters[i].MBB, 0, BranchProbability::getZero()));
433 uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue();
434 uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue();
438 CB->ExtraProb += Clusters[i].Prob;
439 TotalProb += Clusters[i].Prob;
462 BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High,
467 void SwitchCG::sortAndRangeify(CaseClusterVector &Clusters) {
469 for (const CaseCluster &CC : Clusters)
473 llvm::sort(Clusters, [](const CaseCluster &a, const CaseCluster &b) {
478 const unsigned N = Clusters.size();
481 CaseCluster &CC = Clusters[SrcIndex];
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;
492 std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex],
493 sizeof(Clusters[SrcIndex]));
496 Clusters.resize(DstIndex);