Core Core Data Structures

1. Priortiy Queue Population

1.1 Prioriyt Formula

float computePriority(const LiveInterval &LI) {
  float span = LI.getSize();
  float freq = MBFI->getBlockFreq(LI.begin()->valno->def->getParent());
  float weight = span * freq;

  if (TRI->isHinted(LI.reg))
    weight += HINT_BONUS;

  if (GreedyRegClassPriorityTrumpsGlobalness)
    weight += TRI->getRegClassWeight(LI.reg);

  if (GreedyReverseLocalAssignment && !LI.isCrossBB())
    weight = 1.0f / weight;

  return weight;
}

1.2 Queue Initialization

void populateQueue() {
  for (unsigned vReg : LIS->getVirtRegs()) {
    LiveInterval &LI = LIS->getInterval(vReg);
    float prio = computePriority(LI);
    Queue.push(vReg, prio);
  }
}

2. Physical Register Assignment

2.1 Allocation Order Construction

AllocationOrder buildOrder(unsigned vReg) {
  AllocationOrder AO(vReg, TRI, Hints);
  if (SplitThresholdForRegWithHint && hasHint(vReg))
    AO.preferHints();
  return AO;
}

2.2 Interference Check & Costing

unsigned tryAllocate(unsigned vReg) {
  AllocationOrder AO = buildOrder(vReg);
  while (unsigned pReg = AO.next()) {
    switch (Matrix->checkInterference(vReg, pReg)) {
    case IK_Free:
      if (isAcceptable(pReg, vReg)) {
        Matrix->assign(vReg, pReg);
        VRM->setPhys(vReg, pReg);
        return pReg;
      }
      break;
    case IK_VirtReg:
      if (tryEvict(vReg, pReg))
        return pReg;
      break;
    case IK_PhysReg:
      continue; // fixed use, skip
    }
  }
  return ~0u;
}

3. Failure Recovery Pipeline

3.1 Eviction

bool tryEvict(unsigned vReg, unsigned pReg) {
  SmallVector<unsigned, 8> evictees;
  Matrix->collectInterferences(vReg, pReg, evictees);
  if (!EvictAdvisor->profitable(vReg, pReg, evictees))
    return false;

  for (unsigned e : evictees) {
    Matrix->unassign(e);
    VRM->clearPhys(e);
    Queue.push(e, computePriority(LIS->getInterval(e)));
  }
  ++NumEvictions;
  return true;
}

3.2 Live-Range Splitting

3.2.1 Local Split

bool localSplit(unsigned vReg) {
  if (!LIS->getInterval(vReg).isSingleBlock())
    return false;
  float bestGap = findMinGapWeight(vReg);
  unsigned newVReg = splitAtGap(vReg, bestGap);
  Queue.push(newVReg, computePriority(LIS->getInterval(newVReg)));
  return true;
}

3.2.2 Region Split

bool regionSplit(unsigned vReg) {
  SpillPlacement->analyze(vReg);
  SmallVector<BasicBlock*, 4> coldBlocks;
  float splitCost = computeRegionSplitCost(vReg, coldBlocks);
  if (splitCost >= spillCost(vReg))
    return false;
  unsigned newVReg = performRegionSplit(vReg, coldBlocks);
  Queue.push(newVReg, computePriority(LIS->getInterval(newVReg)));
  return true;
}

3.2.3 Block-Level Split

void blockSplit(unsigned vReg) {
  SmallVector<unsigned, 4> fragments;
  splitPerBlock(vReg, fragments);
  for (unsigned f : fragments)
    Queue.push(f, computePriority(LIS->getInterval(f)));
}

3.3 Spilling

unsigned spill(unsigned vReg) {
  if (!LIS->getInterval(vReg).isSpillable())
    return ~0u;

  if (EnableDeferredSpilling) {
    markDeferred(vReg);
    return 0;
  }

  SpillerInstance->spill(vReg);
  ++NumSpills;
  return 0;
}

3.4 Last-Chance Recoloring

unsigned recolor(unsigned vReg, AllocationOrder &AO) {
  if (RecolorDepth >= LastChanceRecoloringMaxDepth)
    return ~0u;
  ++RecolorDepth;
  SmallVector<unsigned, 4> recolored;
  if (tryRecolorInterferences(vReg, AO, recolored)) {
    unsigned pReg = AO.current();
    Matrix->assign(vReg, pReg);
    VRM->setPhys(vReg, pReg);
    --RecolorDepth;
    return pReg;
  }
  --RecolorDepth;
  return ~0u;
}

3.5 CSR First-Time Assignment

unsigned assignCSR(unsigned vReg) {
  float csrCost = computeCSRCost(vReg);
  if (csrCost >= spillCost(vReg) || csrCost >= splitCost(vReg))
    return ~0u;
  unsigned pReg = AO.getUnusedCSR();
  Matrix->assign(vReg, pReg);
  VRM->setPhys(vReg, pReg);
  CostPerUseLimit = 1;
  return pReg;
}

4. Hint-Driven Recoloring Pass

void repairBrokenHints() {
  for (unsigned vReg : BrokenHints) {
    SmallVector<MachineInstr*, 4> copies;
    collectCopies(vReg, copies);
    if (getBrokenHintCost(copies) > 0) {
      tryHintRecolor(vReg);
      ++NumHintRecolorings;
    }
  }
}

5. Post-Allcoation Cleanup

void finalize() {
  removeRedundantCopies();
  SpillerInstance->finalize();
  LiveDebugVariables->emitDebugValues();
  printStatistics();
  releaseTransientData();
}

Debugging Knobs