File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/CodeGen

usr / src / contrib / llvm-project / llvm / lib / CodeGen /

📁 ..
📄 AggressiveAntiDepBreaker.cpp(37.23 KB)
📄 AggressiveAntiDepBreaker.h(6.8 KB)
📄 AllocationOrder.cpp(1.96 KB)
📄 AllocationOrder.h(2.96 KB)
📄 Analysis.cpp(32.62 KB)
📁 AsmPrinter
📄 AtomicExpandPass.cpp(71.86 KB)
📄 BBSectionsPrepare.cpp(18.8 KB)
📄 BasicTargetTransformInfo.cpp(1.53 KB)
📄 BranchFolding.cpp(77.92 KB)
📄 BranchFolding.h(7.36 KB)
📄 BranchRelaxation.cpp(19.45 KB)
📄 BreakFalseDeps.cpp(9.79 KB)
📄 BuiltinGCs.cpp(4.88 KB)
📄 CFGuardLongjmp.cpp(3.73 KB)
📄 CFIInstrInserter.cpp(17.53 KB)
📄 CalcSpillWeights.cpp(10.22 KB)
📄 CallingConvLower.cpp(10.4 KB)
📄 CodeGen.cpp(5.28 KB)
📄 CodeGenPrepare.cpp(295.01 KB)
📄 CommandFlags.cpp(24.89 KB)
📄 CriticalAntiDepBreaker.cpp(27.91 KB)
📄 CriticalAntiDepBreaker.h(4.22 KB)
📄 DFAPacketizer.cpp(10.91 KB)
📄 DeadMachineInstructionElim.cpp(6.52 KB)
📄 DetectDeadLanes.cpp(20.74 KB)
📄 DwarfEHPrepare.cpp(9.01 KB)
📄 EarlyIfConversion.cpp(37.51 KB)
📄 EdgeBundles.cpp(3.21 KB)
📄 ExecutionDomainFix.cpp(14.67 KB)
📄 ExpandMemCmp.cpp(33.66 KB)
📄 ExpandPostRAPseudos.cpp(7.28 KB)
📄 ExpandReductions.cpp(7.23 KB)
📄 FEntryInserter.cpp(1.81 KB)
📄 FaultMaps.cpp(4.99 KB)
📄 FinalizeISel.cpp(2.65 KB)
📄 FixupStatepointCallerSaved.cpp(11.06 KB)
📄 FuncletLayout.cpp(2.21 KB)
📄 GCMetadata.cpp(5.1 KB)
📄 GCMetadataPrinter.cpp(748 B)
📄 GCRootLowering.cpp(11.46 KB)
📄 GCStrategy.cpp(708 B)
📁 GlobalISel
📄 GlobalMerge.cpp(24.52 KB)
📄 HardwareLoops.cpp(18.44 KB)
📄 IfConversion.cpp(89.43 KB)
📄 ImplicitNullChecks.cpp(25.14 KB)
📄 IndirectBrExpandPass.cpp(7.79 KB)
📄 InlineSpiller.cpp(58.24 KB)
📄 InterferenceCache.cpp(8.83 KB)
📄 InterferenceCache.h(7.22 KB)
📄 InterleavedAccessPass.cpp(16.59 KB)
📄 InterleavedLoadCombinePass.cpp(42.35 KB)
📄 IntrinsicLowering.cpp(17.08 KB)
📄 LLVMTargetMachine.cpp(10.25 KB)
📄 LatencyPriorityQueue.cpp(5.64 KB)
📄 LazyMachineBlockFrequencyInfo.cpp(3.36 KB)
📄 LexicalScopes.cpp(12.16 KB)
📄 LiveDebugValues.cpp(78.98 KB)
📄 LiveDebugVariables.cpp(51.79 KB)
📄 LiveDebugVariables.h(2.15 KB)
📄 LiveInterval.cpp(46.67 KB)
📄 LiveIntervalCalc.cpp(7.62 KB)
📄 LiveIntervalUnion.cpp(6.36 KB)
📄 LiveIntervals.cpp(64.59 KB)
📄 LivePhysRegs.cpp(11.08 KB)
📄 LiveRangeCalc.cpp(15.72 KB)
📄 LiveRangeEdit.cpp(17.03 KB)
📄 LiveRangeShrink.cpp(8.69 KB)
📄 LiveRangeUtils.h(2.12 KB)
📄 LiveRegMatrix.cpp(7.47 KB)
📄 LiveRegUnits.cpp(4.72 KB)
📄 LiveStacks.cpp(2.95 KB)
📄 LiveVariables.cpp(30.26 KB)
📄 LocalStackSlotAllocation.cpp(17.26 KB)
📄 LoopTraversal.cpp(2.89 KB)
📄 LowLevelType.cpp(1.93 KB)
📄 LowerEmuTLS.cpp(5.66 KB)
📄 MBFIWrapper.cpp(1.57 KB)
📄 MIRCanonicalizerPass.cpp(12.46 KB)
📄 MIRNamerPass.cpp(2.16 KB)
📁 MIRParser
📄 MIRPrinter.cpp(32.67 KB)
📄 MIRPrintingPass.cpp(1.99 KB)
📄 MIRVRegNamerUtils.cpp(6.04 KB)
📄 MIRVRegNamerUtils.h(3.25 KB)
📄 MachineBasicBlock.cpp(50.47 KB)
📄 MachineBlockFrequencyInfo.cpp(10.13 KB)
📄 MachineBlockPlacement.cpp(137.61 KB)
📄 MachineBranchProbabilityInfo.cpp(3.5 KB)
📄 MachineCSE.cpp(31.82 KB)
📄 MachineCombiner.cpp(28.13 KB)
📄 MachineCopyPropagation.cpp(29.21 KB)
📄 MachineDebugify.cpp(6.47 KB)
📄 MachineDominanceFrontier.cpp(1.83 KB)
📄 MachineDominators.cpp(4.86 KB)
📄 MachineFrameInfo.cpp(9.77 KB)
📄 MachineFunction.cpp(42.97 KB)
📄 MachineFunctionPass.cpp(4.78 KB)
📄 MachineFunctionPrinterPass.cpp(2.3 KB)
📄 MachineInstr.cpp(76.39 KB)
📄 MachineInstrBundle.cpp(11.49 KB)
📄 MachineLICM.cpp(57.05 KB)
📄 MachineLoopInfo.cpp(4.98 KB)
📄 MachineLoopUtils.cpp(5.16 KB)
📄 MachineModuleInfo.cpp(9.9 KB)
📄 MachineModuleInfoImpls.cpp(1.5 KB)
📄 MachineOperand.cpp(39.6 KB)
📄 MachineOptimizationRemarkEmitter.cpp(3.29 KB)
📄 MachineOutliner.cpp(42.13 KB)
📄 MachinePipeliner.cpp(111.33 KB)
📄 MachinePostDominators.cpp(2.42 KB)
📄 MachineRegionInfo.cpp(4.75 KB)
📄 MachineRegisterInfo.cpp(22.97 KB)
📄 MachineSSAUpdater.cpp(12.99 KB)
📄 MachineScheduler.cpp(136.89 KB)
📄 MachineSink.cpp(51.94 KB)
📄 MachineSizeOpts.cpp(8.76 KB)
📄 MachineStripDebug.cpp(3.76 KB)
📄 MachineTraceMetrics.cpp(49.58 KB)
📄 MachineVerifier.cpp(107.98 KB)
📄 MacroFusion.cpp(7.55 KB)
📄 ModuloSchedule.cpp(85.09 KB)
📄 NonRelocatableStringpool.cpp(1.65 KB)
📄 OptimizePHIs.cpp(6.7 KB)
📄 PHIElimination.cpp(27.73 KB)
📄 PHIEliminationUtils.cpp(2.56 KB)
📄 PHIEliminationUtils.h(972 B)
📄 ParallelCG.cpp(3.71 KB)
📄 PatchableFunction.cpp(3.44 KB)
📄 PeepholeOptimizer.cpp(78.41 KB)
📄 PostRAHazardRecognizer.cpp(3.5 KB)
📄 PostRASchedulerList.cpp(24.31 KB)
📄 PreISelIntrinsicLowering.cpp(7.91 KB)
📄 ProcessImplicitDefs.cpp(5.4 KB)
📄 PrologEpilogInserter.cpp(50.45 KB)
📄 PseudoSourceValue.cpp(4.71 KB)
📄 RDFGraph.cpp(58.39 KB)
📄 RDFLiveness.cpp(40.7 KB)
📄 RDFRegisters.cpp(11.29 KB)
📄 ReachingDefAnalysis.cpp(21.74 KB)
📄 RegAllocBase.cpp(6.31 KB)
📄 RegAllocBase.h(4.63 KB)
📄 RegAllocBasic.cpp(11.33 KB)
📄 RegAllocFast.cpp(45.78 KB)
📄 RegAllocGreedy.cpp(123.32 KB)
📄 RegAllocPBQP.cpp(33.14 KB)
📄 RegUsageInfoCollector.cpp(7.39 KB)
📄 RegUsageInfoPropagate.cpp(5.07 KB)
📄 RegisterClassInfo.cpp(6.62 KB)
📄 RegisterCoalescer.cpp(151.71 KB)
📄 RegisterCoalescer.h(4.04 KB)
📄 RegisterPressure.cpp(48.86 KB)
📄 RegisterScavenging.cpp(27.48 KB)
📄 RegisterUsageInfo.cpp(3.18 KB)
📄 RenameIndependentSubregs.cpp(14.79 KB)
📄 ResetMachineFunctionPass.cpp(3.48 KB)
📄 SafeStack.cpp(34.12 KB)
📄 SafeStackLayout.cpp(5.3 KB)
📄 SafeStackLayout.h(2.41 KB)
📄 ScalarizeMaskedMemIntrin.cpp(31.46 KB)
📄 ScheduleDAG.cpp(21.34 KB)
📄 ScheduleDAGInstrs.cpp(54.59 KB)
📄 ScheduleDAGPrinter.cpp(3.21 KB)
📄 ScoreboardHazardRecognizer.cpp(7.96 KB)
📁 SelectionDAG
📄 ShadowStackGCLowering.cpp(14.16 KB)
📄 ShrinkWrap.cpp(23.03 KB)
📄 SjLjEHPrepare.cpp(18.93 KB)
📄 SlotIndexes.cpp(9.35 KB)
📄 SpillPlacement.cpp(12.58 KB)
📄 SpillPlacement.h(6.67 KB)
📄 SplitKit.cpp(66.39 KB)
📄 SplitKit.h(23.7 KB)
📄 StackColoring.cpp(49.03 KB)
📄 StackMapLivenessAnalysis.cpp(6.16 KB)
📄 StackMaps.cpp(19.74 KB)
📄 StackProtector.cpp(22.94 KB)
📄 StackSlotColoring.cpp(17.12 KB)
📄 SwiftErrorValueTracking.cpp(11.37 KB)
📄 SwitchLoweringUtils.cpp(18.33 KB)
📄 TailDuplication.cpp(3.32 KB)
📄 TailDuplicator.cpp(38.29 KB)
📄 TargetFrameLoweringImpl.cpp(6.24 KB)
📄 TargetInstrInfo.cpp(51.1 KB)
📄 TargetLoweringBase.cpp(82.53 KB)
📄 TargetLoweringObjectFileImpl.cpp(80.52 KB)
📄 TargetOptionsImpl.cpp(2 KB)
📄 TargetPassConfig.cpp(48.89 KB)
📄 TargetRegisterInfo.cpp(19.15 KB)
📄 TargetSchedule.cpp(13.16 KB)
📄 TargetSubtargetInfo.cpp(1.89 KB)
📄 TwoAddressInstructionPass.cpp(62.08 KB)
📄 TypePromotion.cpp(32.46 KB)
📄 UnreachableBlockElim.cpp(7.48 KB)
📄 ValueTypes.cpp(19.87 KB)
📄 VirtRegMap.cpp(21.4 KB)
📄 WasmEHPrepare.cpp(17.48 KB)
📄 WinEHPrepare.cpp(51.16 KB)
📄 XRayInstrumentation.cpp(9.66 KB)

Editing: SwitchLoweringUtils.cpp

//===- SwitchLoweringUtils.cpp - Switch Lowering --------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains switch inst lowering optimizations and utilities for
// codegen, so that it can be used for both SelectionDAG and GlobalISel.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/SwitchLoweringUtils.h"
#include "llvm/Target/TargetMachine.h"

using namespace llvm;
using namespace SwitchCG;

uint64_t SwitchCG::getJumpTableRange(const CaseClusterVector &Clusters,
                                     unsigned First, unsigned Last) {
  assert(Last >= First);
  const APInt &LowCase = Clusters[First].Low->getValue();
  const 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.
  return (HighCase - LowCase).getLimitedValue((UINT64_MAX - 1) / 100) + 1;
}

uint64_t
SwitchCG::getJumpTableNumCases(const SmallVectorImpl<unsigned> &TotalCases,
                               unsigned First, unsigned Last) {
  assert(Last >= First);
  assert(TotalCases[Last] >= TotalCases[First]);
  uint64_t NumCases =
      TotalCases[Last] - (First == 0 ? 0 : TotalCases[First - 1]);
  return NumCases;
}

void SwitchCG::SwitchLowering::findJumpTables(CaseClusterVector &Clusters,
                                              const SwitchInst *SI,
                                              MachineBasicBlock *DefaultMBB,
                                              ProfileSummaryInfo *PSI,
                                              BlockFrequencyInfo *BFI) {
#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

assert(TLI && "TLI not set!");
  if (!TLI->areJTsAllowed(SI->getParent()->getParent()))
    return;

const unsigned MinJumpTableEntries = TLI->getMinimumJumpTableEntries();
  const unsigned SmallNumberOfEntries = MinJumpTableEntries / 2;

// Bail if not enough cases.
  const int64_t N = Clusters.size();
  if (N < 2 || N < MinJumpTableEntries)
    return;

// Accumulated number of cases in each cluster and those prior to it.
  SmallVector<unsigned, 8> TotalCases(N);
  for (unsigned i = 0; i < N; ++i) {
    const APInt &Hi = Clusters[i].High->getValue();
    const APInt &Lo = Clusters[i].Low->getValue();
    TotalCases[i] = (Hi - Lo).getLimitedValue() + 1;
    if (i != 0)
      TotalCases[i] += TotalCases[i - 1];
  }

uint64_t Range = getJumpTableRange(Clusters,0, N - 1);
  uint64_t NumCases = getJumpTableNumCases(TotalCases, 0, N - 1);
  assert(NumCases < UINT64_MAX / 100);
  assert(Range >= NumCases);

// Cheap case: the whole range may be suitable for jump table.
  if (TLI->isSuitableForJumpTable(SI, NumCases, Range, PSI, BFI)) {
    CaseCluster JTCluster;
    if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) {
      Clusters[0] = JTCluster;
      Clusters.resize(1);
      return;
    }
  }

// The algorithm below is not suitable for -O0.
  if (TM->getOptLevel() == CodeGenOpt::None)
    return;

// 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);
  // PartitionsScore[i] is used to break ties when choosing between two
  // partitionings resulting in the same number of partitions.
  SmallVector<unsigned, 8> PartitionsScore(N);
  // For PartitionsScore, a small number of comparisons is considered as good as
  // a jump table and a single comparison is considered better than a jump
  // table.
  enum PartitionScores : unsigned {
    NoTable = 0,
    Table = 1,
    FewCases = 1,
    SingleCase = 2
  };

// Base case: There is only one way to partition Clusters[N-1].
  MinPartitions[N - 1] = 1;
  LastElement[N - 1] = N - 1;
  PartitionsScore[N - 1] = PartitionScores::SingleCase;

// 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;
    PartitionsScore[i] = PartitionsScore[i + 1] + PartitionScores::SingleCase;

// 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].
      Range = getJumpTableRange(Clusters, i, j);
      NumCases = getJumpTableNumCases(TotalCases, i, j);
      assert(NumCases < UINT64_MAX / 100);
      assert(Range >= NumCases);

if (TLI->isSuitableForJumpTable(SI, NumCases, Range, PSI, BFI)) {
        unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
        unsigned Score = j == N - 1 ? 0 : PartitionsScore[j + 1];
        int64_t NumEntries = j - i + 1;

if (NumEntries == 1)
          Score += PartitionScores::SingleCase;
        else if (NumEntries <= SmallNumberOfEntries)
          Score += PartitionScores::FewCases;
        else if (NumEntries >= MinJumpTableEntries)
          Score += PartitionScores::Table;

// If this leads to fewer partitions, or to the same number of
        // partitions with better score, it is a better partitioning.
        if (NumPartitions < MinPartitions[i] ||
            (NumPartitions == MinPartitions[i] && Score > PartitionsScore[i])) {
          MinPartitions[i] = NumPartitions;
          LastElement[i] = j;
          PartitionsScore[i] = Score;
        }
      }
    }
  }

// 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 >= MinJumpTableEntries &&
        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 SwitchCG::SwitchLowering::buildJumpTable(const CaseClusterVector &Clusters,
                                              unsigned First, unsigned Last,
                                              const SwitchInst *SI,
                                              MachineBasicBlock *DefaultMBB,
                                              CaseCluster &JTCluster) {
  assert(First <= Last);

auto Prob = BranchProbability::getZero();
  unsigned NumCmps = 0;
  std::vector<MachineBasicBlock*> Table;
  DenseMap<MachineBasicBlock*, BranchProbability> JTProbs;

// Initialize probabilities in JTProbs.
  for (unsigned I = First; I <= Last; ++I)
    JTProbs[Clusters[I].MBB] = BranchProbability::getZero();

for (unsigned I = First; I <= Last; ++I) {
    assert(Clusters[I].Kind == CC_Range);
    Prob += Clusters[I].Prob;
    const APInt &Low = Clusters[I].Low->getValue();
    const APInt &High = Clusters[I].High->getValue();
    NumCmps += (Low == High) ? 1 : 2;
    if (I != First) {
      // Fill the gap between this and the previous cluster.
      const 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);
    }
    uint64_t ClusterSize = (High - Low).getLimitedValue() + 1;
    for (uint64_t J = 0; J < ClusterSize; ++J)
      Table.push_back(Clusters[I].MBB);
    JTProbs[Clusters[I].MBB] += Clusters[I].Prob;
  }

unsigned NumDests = JTProbs.size();
  if (TLI->isSuitableForBitTests(NumDests, NumCmps,
                                 Clusters[First].Low->getValue(),
                                 Clusters[Last].High->getValue(), *DL)) {
    // 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;
    addSuccessorWithProb(JumpTableMBB, Succ, JTProbs[Succ]);
    Done.insert(Succ);
  }
  JumpTableMBB->normalizeSuccProbs();

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.emplace_back(std::move(JTH), std::move(JT));

JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High,
                                     JTCases.size() - 1, Prob);
  return true;
}

void SwitchCG::SwitchLowering::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

// The algorithm below is not suitable for -O0.
  if (TM->getOptLevel() == CodeGenOpt::None)
    return;

// If target does not have legal shift left, do not emit bit tests at all.
  EVT PTy = TLI->getPointerTy(*DL);
  if (!TLI->isOperationLegal(ISD::SHL, PTy))
    return;

int BitWidth = PTy.getSizeInBits();
  const int64_t N = Clusters.size();

// 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 (!TLI->rangeFitsInWord(Clusters[i].Low->getValue(),
                                Clusters[j].High->getValue(), *DL))
        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 {
      size_t NumClusters = Last - First + 1;
      std::memmove(&Clusters[DstIndex], &Clusters[First],
                   sizeof(Clusters[0]) * NumClusters);
      DstIndex += NumClusters;
    }
  }
  Clusters.resize(DstIndex);
}

bool SwitchCG::SwitchLowering::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 (!TLI->isSuitableForBitTests(NumDests, NumCmps, Low, High, *DL))
    return false;

APInt LowBound;
  APInt CmpRange;

const int BitWidth = TLI->getPointerTy(*DL).getSizeInBits();
  assert(TLI->rangeFitsInWord(Low, High, *DL) &&
         "Case range must fit in bit mask!");

// Check if the clusters cover a contiguous range such that no value in the
  // range will jump to the default statement.
  bool ContiguousRange = true;
  for (int64_t I = First + 1; I <= Last; ++I) {
    if (Clusters[I].Low->getValue() != Clusters[I - 1].High->getValue() + 1) {
      ContiguousRange = false;
      break;
    }
  }

if (Low.isStrictlyPositive() && 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;
    ContiguousRange = false;
  } else {
    LowBound = Low;
    CmpRange = High - Low;
  }

CaseBitsVector CBV;
  auto TotalProb = BranchProbability::getZero();
  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, BranchProbability::getZero()));
    CaseBits *CB = &CBV[j];

// Update Mask, Bits and ExtraProb.
    uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue();
    uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue();
    assert(Hi >= Lo && Hi < 64 && "Invalid bit case!");
    CB->Mask |= (-1ULL >> (63 - (Hi - Lo))) << Lo;
    CB->Bits += Hi - Lo + 1;
    CB->ExtraProb += Clusters[i].Prob;
    TotalProb += Clusters[i].Prob;
  }

BitTestInfo BTI;
  llvm::sort(CBV, [](const CaseBits &a, const CaseBits &b) {
    // Sort by probability first, number of bits second, bit mask third.
    if (a.ExtraProb != b.ExtraProb)
      return a.ExtraProb > b.ExtraProb;
    if (a.Bits != b.Bits)
      return a.Bits > b.Bits;
    return a.Mask < b.Mask;
  });

for (auto &CB : CBV) {
    MachineBasicBlock *BitTestBB =
        FuncInfo.MF->CreateMachineBasicBlock(SI->getParent());
    BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraProb));
  }
  BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange),
                            SI->getCondition(), -1U, MVT::Other, false,
                            ContiguousRange, nullptr, nullptr, std::move(BTI),
                            TotalProb);

BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High,
                                    BitTestCases.size() - 1, TotalProb);
  return true;
}

void SwitchCG::sortAndRangeify(CaseClusterVector &Clusters) {
#ifndef NDEBUG
  for (const CaseCluster &CC : Clusters)
    assert(CC.Low == CC.High && "Input clusters must be single-case");
#endif

llvm::sort(Clusters, [](const CaseCluster &a, const CaseCluster &b) {
    return a.Low->getValue().slt(b.Low->getValue());
  });

// Merge adjacent clusters with the same destination.
  const unsigned N = Clusters.size();
  unsigned DstIndex = 0;
  for (unsigned SrcIndex = 0; SrcIndex < N; ++SrcIndex) {
    CaseCluster &CC = Clusters[SrcIndex];
    const ConstantInt *CaseVal = CC.Low;
    MachineBasicBlock *Succ = CC.MBB;

if (DstIndex != 0 && Clusters[DstIndex - 1].MBB == Succ &&
        (CaseVal->getValue() - Clusters[DstIndex - 1].High->getValue()) == 1) {
      // If this case has the same successor and is a neighbour, merge it into
      // the previous cluster.
      Clusters[DstIndex - 1].High = CaseVal;
      Clusters[DstIndex - 1].Prob += CC.Prob;
    } else {
      std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex],
                   sizeof(Clusters[SrcIndex]));
    }
  }
  Clusters.resize(DstIndex);
}

003 File Manager

Editing: SwitchLoweringUtils.cpp

Upload File

Create Folder