1937 lines · cpp
1//===- SplitKit.cpp - Toolkit for splitting live ranges -------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains the SplitAnalysis class as well as mutator functions for10// live range splitting.11//12//===----------------------------------------------------------------------===//13 14#include "SplitKit.h"15#include "llvm/ADT/STLExtras.h"16#include "llvm/ADT/Statistic.h"17#include "llvm/CodeGen/LiveRangeEdit.h"18#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"19#include "llvm/CodeGen/MachineDominators.h"20#include "llvm/CodeGen/MachineInstr.h"21#include "llvm/CodeGen/MachineInstrBuilder.h"22#include "llvm/CodeGen/MachineLoopInfo.h"23#include "llvm/CodeGen/MachineOperand.h"24#include "llvm/CodeGen/MachineRegisterInfo.h"25#include "llvm/CodeGen/TargetInstrInfo.h"26#include "llvm/CodeGen/TargetOpcodes.h"27#include "llvm/CodeGen/TargetRegisterInfo.h"28#include "llvm/CodeGen/TargetSubtargetInfo.h"29#include "llvm/CodeGen/VirtRegMap.h"30#include "llvm/Config/llvm-config.h"31#include "llvm/IR/DebugLoc.h"32#include "llvm/Support/Allocator.h"33#include "llvm/Support/BlockFrequency.h"34#include "llvm/Support/Debug.h"35#include "llvm/Support/ErrorHandling.h"36#include "llvm/Support/raw_ostream.h"37#include <algorithm>38#include <cassert>39#include <iterator>40#include <limits>41#include <tuple>42 43using namespace llvm;44 45#define DEBUG_TYPE "regalloc"46 47static cl::opt<bool>48 EnableLoopIVHeuristic("enable-split-loopiv-heuristic",49 cl::desc("Enable loop iv regalloc heuristic"),50 cl::init(true));51 52STATISTIC(NumFinished, "Number of splits finished");53STATISTIC(NumSimple, "Number of splits that were simple");54STATISTIC(NumCopies, "Number of copies inserted for splitting");55STATISTIC(NumRemats, "Number of rematerialized defs for splitting");56 57//===----------------------------------------------------------------------===//58// Last Insert Point Analysis59//===----------------------------------------------------------------------===//60 61InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,62 unsigned BBNum)63 : LIS(lis), LastInsertPoint(BBNum) {}64 65SlotIndex66InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,67 const MachineBasicBlock &MBB) {68 unsigned Num = MBB.getNumber();69 std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];70 SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);71 72 SmallVector<const MachineBasicBlock *, 1> ExceptionalSuccessors;73 bool EHPadSuccessor = false;74 for (const MachineBasicBlock *SMBB : MBB.successors()) {75 if (SMBB->isEHPad()) {76 ExceptionalSuccessors.push_back(SMBB);77 EHPadSuccessor = true;78 } else if (SMBB->isInlineAsmBrIndirectTarget())79 ExceptionalSuccessors.push_back(SMBB);80 }81 82 // Compute insert points on the first call. The pair is independent of the83 // current live interval.84 if (!LIP.first.isValid()) {85 MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator();86 if (FirstTerm == MBB.end())87 LIP.first = MBBEnd;88 else89 LIP.first = LIS.getInstructionIndex(*FirstTerm);90 91 // If there is a landing pad or inlineasm_br successor, also find the92 // instruction. If there is no such instruction, we don't need to do93 // anything special. We assume there cannot be multiple instructions that94 // are Calls with EHPad successors or INLINEASM_BR in a block. Further, we95 // assume that if there are any, they will be after any other call96 // instructions in the block.97 if (ExceptionalSuccessors.empty())98 return LIP.first;99 for (const MachineInstr &MI : llvm::reverse(MBB)) {100 if ((EHPadSuccessor && MI.isCall()) ||101 MI.getOpcode() == TargetOpcode::INLINEASM_BR) {102 LIP.second = LIS.getInstructionIndex(MI);103 break;104 }105 }106 }107 108 // If CurLI is live into a landing pad successor, move the last insert point109 // back to the call that may throw.110 if (!LIP.second)111 return LIP.first;112 113 if (none_of(ExceptionalSuccessors, [&](const MachineBasicBlock *EHPad) {114 return LIS.isLiveInToMBB(CurLI, EHPad);115 }))116 return LIP.first;117 118 // Find the value leaving MBB.119 const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);120 if (!VNI)121 return LIP.first;122 123 // The def of statepoint instruction is a gc relocation and it should be alive124 // in landing pad. So we cannot split interval after statepoint instruction.125 if (SlotIndex::isSameInstr(VNI->def, LIP.second))126 if (auto *I = LIS.getInstructionFromIndex(LIP.second))127 if (I->getOpcode() == TargetOpcode::STATEPOINT)128 return LIP.second;129 130 // If the value leaving MBB was defined after the call in MBB, it can't131 // really be live-in to the landing pad. This can happen if the landing pad132 // has a PHI, and this register is undef on the exceptional edge.133 if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)134 return LIP.first;135 136 // Value is properly live-in to the landing pad.137 // Only allow inserts before the call.138 return LIP.second;139}140 141MachineBasicBlock::iterator142InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI,143 MachineBasicBlock &MBB) {144 SlotIndex LIP = getLastInsertPoint(CurLI, MBB);145 if (LIP == LIS.getMBBEndIdx(&MBB))146 return MBB.end();147 return LIS.getInstructionFromIndex(LIP);148}149 150//===----------------------------------------------------------------------===//151// Split Analysis152//===----------------------------------------------------------------------===//153 154SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,155 const MachineLoopInfo &mli)156 : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),157 TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}158 159void SplitAnalysis::clear() {160 UseSlots.clear();161 UseBlocks.clear();162 ThroughBlocks.clear();163 CurLI = nullptr;164}165 166/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.167void SplitAnalysis::analyzeUses() {168 assert(UseSlots.empty() && "Call clear first");169 170 // First get all the defs from the interval values. This provides the correct171 // slots for early clobbers.172 for (const VNInfo *VNI : CurLI->valnos)173 if (!VNI->isPHIDef() && !VNI->isUnused())174 UseSlots.push_back(VNI->def);175 176 // Get use slots form the use-def chain.177 const MachineRegisterInfo &MRI = MF.getRegInfo();178 for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg()))179 if (!MO.isUndef())180 UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());181 182 array_pod_sort(UseSlots.begin(), UseSlots.end());183 184 // Remove duplicates, keeping the smaller slot for each instruction.185 // That is what we want for early clobbers.186 UseSlots.erase(llvm::unique(UseSlots, SlotIndex::isSameInstr),187 UseSlots.end());188 189 // Compute per-live block info.190 calcLiveBlockInfo();191 192 LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "193 << UseBlocks.size() << " blocks, through "194 << NumThroughBlocks << " blocks.\n");195}196 197/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks198/// where CurLI is live.199void SplitAnalysis::calcLiveBlockInfo() {200 ThroughBlocks.resize(MF.getNumBlockIDs());201 NumThroughBlocks = NumGapBlocks = 0;202 if (CurLI->empty())203 return;204 205 LiveInterval::const_iterator LVI = CurLI->begin();206 LiveInterval::const_iterator LVE = CurLI->end();207 208 SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;209 UseI = UseSlots.begin();210 UseE = UseSlots.end();211 212 // Loop over basic blocks where CurLI is live.213 MachineFunction::iterator MFI =214 LIS.getMBBFromIndex(LVI->start)->getIterator();215 while (true) {216 BlockInfo BI;217 BI.MBB = &*MFI;218 SlotIndex Start, Stop;219 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);220 221 // If the block contains no uses, the range must be live through. At one222 // point, RegisterCoalescer could create dangling ranges that ended223 // mid-block.224 if (UseI == UseE || *UseI >= Stop) {225 ++NumThroughBlocks;226 ThroughBlocks.set(BI.MBB->getNumber());227 // The range shouldn't end mid-block if there are no uses. This shouldn't228 // happen.229 assert(LVI->end >= Stop && "range ends mid block with no uses");230 } else {231 // This block has uses. Find the first and last uses in the block.232 BI.FirstInstr = *UseI;233 assert(BI.FirstInstr >= Start);234 do ++UseI;235 while (UseI != UseE && *UseI < Stop);236 BI.LastInstr = UseI[-1];237 assert(BI.LastInstr < Stop);238 239 // LVI is the first live segment overlapping MBB.240 BI.LiveIn = LVI->start <= Start;241 242 // When not live in, the first use should be a def.243 if (!BI.LiveIn) {244 assert(LVI->start == LVI->valno->def && "Dangling Segment start");245 assert(LVI->start == BI.FirstInstr && "First instr should be a def");246 BI.FirstDef = BI.FirstInstr;247 }248 249 // Look for gaps in the live range.250 BI.LiveOut = true;251 while (LVI->end < Stop) {252 SlotIndex LastStop = LVI->end;253 if (++LVI == LVE || LVI->start >= Stop) {254 BI.LiveOut = false;255 BI.LastInstr = LastStop;256 break;257 }258 259 if (LastStop < LVI->start) {260 // There is a gap in the live range. Create duplicate entries for the261 // live-in snippet and the live-out snippet.262 ++NumGapBlocks;263 264 // Push the Live-in part.265 BI.LiveOut = false;266 UseBlocks.push_back(BI);267 UseBlocks.back().LastInstr = LastStop;268 269 // Set up BI for the live-out part.270 BI.LiveIn = false;271 BI.LiveOut = true;272 BI.FirstInstr = BI.FirstDef = LVI->start;273 }274 275 // A Segment that starts in the middle of the block must be a def.276 assert(LVI->start == LVI->valno->def && "Dangling Segment start");277 if (!BI.FirstDef)278 BI.FirstDef = LVI->start;279 }280 281 UseBlocks.push_back(BI);282 283 // LVI is now at LVE or LVI->end >= Stop.284 if (LVI == LVE)285 break;286 }287 288 // Live segment ends exactly at Stop. Move to the next segment.289 if (LVI->end == Stop && ++LVI == LVE)290 break;291 292 // Pick the next basic block.293 if (LVI->start < Stop)294 ++MFI;295 else296 MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();297 }298 299 LooksLikeLoopIV = EnableLoopIVHeuristic && UseBlocks.size() == 2 &&300 any_of(UseBlocks, [this](BlockInfo &BI) {301 MachineLoop *L = Loops.getLoopFor(BI.MBB);302 return BI.LiveIn && BI.LiveOut && BI.FirstDef && L &&303 L->isLoopLatch(BI.MBB);304 });305 306 assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");307}308 309unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {310 if (cli->empty())311 return 0;312 LiveInterval *li = const_cast<LiveInterval*>(cli);313 LiveInterval::iterator LVI = li->begin();314 LiveInterval::iterator LVE = li->end();315 unsigned Count = 0;316 317 // Loop over basic blocks where li is live.318 MachineFunction::const_iterator MFI =319 LIS.getMBBFromIndex(LVI->start)->getIterator();320 SlotIndex Stop = LIS.getMBBEndIdx(&*MFI);321 while (true) {322 ++Count;323 LVI = li->advanceTo(LVI, Stop);324 if (LVI == LVE)325 return Count;326 do {327 ++MFI;328 Stop = LIS.getMBBEndIdx(&*MFI);329 } while (Stop <= LVI->start);330 }331}332 333bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {334 Register OrigReg = VRM.getOriginal(CurLI->reg());335 const LiveInterval &Orig = LIS.getInterval(OrigReg);336 assert(!Orig.empty() && "Splitting empty interval?");337 LiveInterval::const_iterator I = Orig.find(Idx);338 339 // Range containing Idx should begin at Idx.340 if (I != Orig.end() && I->start <= Idx)341 return I->start == Idx;342 343 // Range does not contain Idx, previous must end at Idx.344 return I != Orig.begin() && (--I)->end == Idx;345}346 347void SplitAnalysis::analyze(const LiveInterval *li) {348 clear();349 CurLI = li;350 analyzeUses();351}352 353//===----------------------------------------------------------------------===//354// Split Editor355//===----------------------------------------------------------------------===//356 357/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.358SplitEditor::SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM,359 MachineDominatorTree &MDT,360 MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI)361 : SA(SA), LIS(LIS), VRM(VRM), MRI(VRM.getMachineFunction().getRegInfo()),362 MDT(MDT), TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()),363 TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()),364 MBFI(MBFI), VRAI(VRAI), RegAssign(Allocator) {}365 366void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {367 Edit = &LRE;368 SpillMode = SM;369 OpenIdx = 0;370 RegAssign.clear();371 Values.clear();372 373 // Reset the LiveIntervalCalc instances needed for this spill mode.374 LICalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,375 &LIS.getVNInfoAllocator());376 if (SpillMode)377 LICalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,378 &LIS.getVNInfoAllocator());379}380 381#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)382LLVM_DUMP_METHOD void SplitEditor::dump() const {383 if (RegAssign.empty()) {384 dbgs() << " empty\n";385 return;386 }387 388 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)389 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();390 dbgs() << '\n';391}392#endif393 394/// Find a subrange corresponding to the exact lane mask @p LM in the live395/// interval @p LI. The interval @p LI is assumed to contain such a subrange.396/// This function is used to find corresponding subranges between the397/// original interval and the new intervals.398template <typename T> auto &getSubrangeImpl(LaneBitmask LM, T &LI) {399 for (auto &S : LI.subranges())400 if (S.LaneMask == LM)401 return S;402 llvm_unreachable("SubRange for this mask not found");403}404 405LiveInterval::SubRange &getSubRangeForMaskExact(LaneBitmask LM,406 LiveInterval &LI) {407 return getSubrangeImpl(LM, LI);408}409 410const LiveInterval::SubRange &getSubRangeForMaskExact(LaneBitmask LM,411 const LiveInterval &LI) {412 return getSubrangeImpl(LM, LI);413}414 415/// Find a subrange corresponding to the lane mask @p LM, or a superset of it,416/// in the live interval @p LI. The interval @p LI is assumed to contain such417/// a subrange. This function is used to find corresponding subranges between418/// the original interval and the new intervals.419const LiveInterval::SubRange &getSubRangeForMask(LaneBitmask LM,420 const LiveInterval &LI) {421 for (const LiveInterval::SubRange &S : LI.subranges())422 if ((S.LaneMask & LM) == LM)423 return S;424 llvm_unreachable("SubRange for this mask not found");425}426 427void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {428 if (!LI.hasSubRanges()) {429 LI.createDeadDef(VNI);430 return;431 }432 433 SlotIndex Def = VNI->def;434 if (Original) {435 // If we are transferring a def from the original interval, make sure436 // to only update the subranges for which the original subranges had437 // a def at this location.438 for (LiveInterval::SubRange &S : LI.subranges()) {439 auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());440 VNInfo *PV = PS.getVNInfoAt(Def);441 if (PV != nullptr && PV->def == Def)442 S.createDeadDef(Def, LIS.getVNInfoAllocator());443 }444 } else {445 // This is a new def: either from rematerialization, or from an inserted446 // copy. Since rematerialization can regenerate a definition of a sub-447 // register, we need to check which subranges need to be updated.448 const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def);449 assert(DefMI != nullptr);450 LaneBitmask LM;451 for (const MachineOperand &DefOp : DefMI->defs()) {452 Register R = DefOp.getReg();453 if (R != LI.reg())454 continue;455 if (unsigned SR = DefOp.getSubReg())456 LM |= TRI.getSubRegIndexLaneMask(SR);457 else {458 LM = MRI.getMaxLaneMaskForVReg(R);459 break;460 }461 }462 for (LiveInterval::SubRange &S : LI.subranges())463 if ((S.LaneMask & LM).any())464 S.createDeadDef(Def, LIS.getVNInfoAllocator());465 }466}467 468VNInfo *SplitEditor::defValue(unsigned RegIdx,469 const VNInfo *ParentVNI,470 SlotIndex Idx,471 bool Original) {472 assert(ParentVNI && "Mapping NULL value");473 assert(Idx.isValid() && "Invalid SlotIndex");474 assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");475 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));476 477 // Create a new value.478 VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());479 480 bool Force = LI->hasSubRanges();481 ValueForcePair FP(Force ? nullptr : VNI, Force);482 // Use insert for lookup, so we can add missing values with a second lookup.483 std::pair<ValueMap::iterator, bool> InsP =484 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));485 486 // This was the first time (RegIdx, ParentVNI) was mapped, and it is not487 // forced. Keep it as a simple def without any liveness.488 if (!Force && InsP.second)489 return VNI;490 491 // If the previous value was a simple mapping, add liveness for it now.492 if (VNInfo *OldVNI = InsP.first->second.getPointer()) {493 addDeadDef(*LI, OldVNI, Original);494 495 // No longer a simple mapping. Switch to a complex mapping. If the496 // interval has subranges, make it a forced mapping.497 InsP.first->second = ValueForcePair(nullptr, Force);498 }499 500 // This is a complex mapping, add liveness for VNI501 addDeadDef(*LI, VNI, Original);502 return VNI;503}504 505void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) {506 ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];507 VNInfo *VNI = VFP.getPointer();508 509 // ParentVNI was either unmapped or already complex mapped. Either way, just510 // set the force bit.511 if (!VNI) {512 VFP.setInt(true);513 return;514 }515 516 // This was previously a single mapping. Make sure the old def is represented517 // by a trivial live range.518 addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);519 520 // Mark as complex mapped, forced.521 VFP = ValueForcePair(nullptr, true);522}523 524SlotIndex SplitEditor::buildSingleSubRegCopy(525 Register FromReg, Register ToReg, MachineBasicBlock &MBB,526 MachineBasicBlock::iterator InsertBefore, unsigned SubIdx,527 LiveInterval &DestLI, bool Late, SlotIndex Def, const MCInstrDesc &Desc) {528 bool FirstCopy = !Def.isValid();529 MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc)530 .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy)531 | getInternalReadRegState(!FirstCopy), SubIdx)532 .addReg(FromReg, 0, SubIdx);533 534 SlotIndexes &Indexes = *LIS.getSlotIndexes();535 if (FirstCopy) {536 Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();537 } else {538 CopyMI->bundleWithPred();539 }540 return Def;541}542 543SlotIndex SplitEditor::buildCopy(Register FromReg, Register ToReg,544 LaneBitmask LaneMask, MachineBasicBlock &MBB,545 MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) {546 const MCInstrDesc &Desc =547 TII.get(TII.getLiveRangeSplitOpcode(FromReg, *MBB.getParent()));548 SlotIndexes &Indexes = *LIS.getSlotIndexes();549 if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) {550 // The full vreg is copied.551 MachineInstr *CopyMI =552 BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg);553 return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();554 }555 556 // Only a subset of lanes needs to be copied. The following is a simple557 // heuristic to construct a sequence of COPYs. We could add a target558 // specific callback if this turns out to be suboptimal.559 LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx));560 561 // First pass: Try to find a perfectly matching subregister index. If none562 // exists find the one covering the most lanemask bits.563 const TargetRegisterClass *RC = MRI.getRegClass(FromReg);564 assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class");565 566 SmallVector<unsigned, 8> SubIndexes;567 568 // Abort if we cannot possibly implement the COPY with the given indexes.569 if (!TRI.getCoveringSubRegIndexes(RC, LaneMask, SubIndexes))570 report_fatal_error("Impossible to implement partial COPY");571 572 SlotIndex Def;573 for (unsigned BestIdx : SubIndexes) {574 Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,575 DestLI, Late, Def, Desc);576 }577 578 BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();579 DestLI.refineSubRanges(580 Allocator, LaneMask,581 [Def, &Allocator](LiveInterval::SubRange &SR) {582 SR.createDeadDef(Def, Allocator);583 },584 Indexes, TRI);585 586 return Def;587}588 589bool SplitEditor::rematWillIncreaseRestriction(const MachineInstr *DefMI,590 MachineBasicBlock &MBB,591 SlotIndex UseIdx) const {592 const MachineInstr *UseMI = LIS.getInstructionFromIndex(UseIdx);593 if (!UseMI)594 return false;595 596 // Currently code assumes rematerialization only happens for a def at 0.597 const unsigned DefOperandIdx = 0;598 // We want to compute the static register class constraint for the instruction599 // def. If it is a smaller subclass than getLargestLegalSuperClass at the use600 // site, then rematerializing it will increase the constraints.601 const TargetRegisterClass *DefConstrainRC =602 DefMI->getRegClassConstraint(DefOperandIdx, &TII, &TRI);603 if (!DefConstrainRC)604 return false;605 606 const TargetRegisterClass *RC = MRI.getRegClass(Edit->getReg());607 608 // We want to find the register class that can be inflated to after the split609 // occurs in recomputeRegClass610 const TargetRegisterClass *SuperRC =611 TRI.getLargestLegalSuperClass(RC, *MBB.getParent());612 613 Register DefReg = DefMI->getOperand(DefOperandIdx).getReg();614 const TargetRegisterClass *UseConstrainRC =615 UseMI->getRegClassConstraintEffectForVReg(DefReg, SuperRC, &TII, &TRI,616 /*ExploreBundle=*/true);617 return UseConstrainRC->hasSubClass(DefConstrainRC);618}619 620VNInfo *SplitEditor::defFromParent(unsigned RegIdx, const VNInfo *ParentVNI,621 SlotIndex UseIdx, MachineBasicBlock &MBB,622 MachineBasicBlock::iterator I) {623 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));624 625 // We may be trying to avoid interference that ends at a deleted instruction,626 // so always begin RegIdx 0 early and all others late.627 bool Late = RegIdx != 0;628 629 // Attempt cheap-as-a-copy rematerialization.630 Register Original = VRM.getOriginal(Edit->get(RegIdx));631 LiveInterval &OrigLI = LIS.getInterval(Original);632 VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);633 634 Register Reg = LI->reg();635 if (OrigVNI) {636 LiveRangeEdit::Remat RM(ParentVNI);637 RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);638 if (RM.OrigMI && TII.isAsCheapAsAMove(*RM.OrigMI) &&639 Edit->canRematerializeAt(RM, UseIdx)) {640 if (!rematWillIncreaseRestriction(RM.OrigMI, MBB, UseIdx)) {641 SlotIndex Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late);642 ++NumRemats;643 // Define the value in Reg.644 return defValue(RegIdx, ParentVNI, Def, false);645 }646 LLVM_DEBUG(647 dbgs() << "skipping rematerialize of " << printReg(Reg) << " at "648 << UseIdx649 << " since it will increase register class restrictions\n");650 }651 }652 653 LaneBitmask LaneMask;654 if (OrigLI.hasSubRanges()) {655 LaneMask = LaneBitmask::getNone();656 for (LiveInterval::SubRange &S : OrigLI.subranges()) {657 if (S.liveAt(UseIdx))658 LaneMask |= S.LaneMask;659 }660 } else {661 LaneMask = LaneBitmask::getAll();662 }663 664 SlotIndex Def;665 if (LaneMask.none()) {666 const MCInstrDesc &Desc = TII.get(TargetOpcode::IMPLICIT_DEF);667 MachineInstr *ImplicitDef = BuildMI(MBB, I, DebugLoc(), Desc, Reg);668 SlotIndexes &Indexes = *LIS.getSlotIndexes();669 Def = Indexes.insertMachineInstrInMaps(*ImplicitDef, Late).getRegSlot();670 } else {671 ++NumCopies;672 Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx);673 }674 675 // Define the value in Reg.676 return defValue(RegIdx, ParentVNI, Def, false);677}678 679/// Create a new virtual register and live interval.680unsigned SplitEditor::openIntv() {681 // Create the complement as index 0.682 if (Edit->empty())683 Edit->createEmptyInterval();684 685 // Create the open interval.686 OpenIdx = Edit->size();687 Edit->createEmptyInterval();688 return OpenIdx;689}690 691void SplitEditor::selectIntv(unsigned Idx) {692 assert(Idx != 0 && "Cannot select the complement interval");693 assert(Idx < Edit->size() && "Can only select previously opened interval");694 LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n');695 OpenIdx = Idx;696}697 698SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {699 assert(OpenIdx && "openIntv not called before enterIntvBefore");700 LLVM_DEBUG(dbgs() << " enterIntvBefore " << Idx);701 Idx = Idx.getBaseIndex();702 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);703 if (!ParentVNI) {704 LLVM_DEBUG(dbgs() << ": not live\n");705 return Idx;706 }707 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');708 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);709 assert(MI && "enterIntvBefore called with invalid index");710 711 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);712 return VNI->def;713}714 715SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) {716 assert(OpenIdx && "openIntv not called before enterIntvAfter");717 LLVM_DEBUG(dbgs() << " enterIntvAfter " << Idx);718 Idx = Idx.getBoundaryIndex();719 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);720 if (!ParentVNI) {721 LLVM_DEBUG(dbgs() << ": not live\n");722 return Idx;723 }724 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');725 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);726 assert(MI && "enterIntvAfter called with invalid index");727 728 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),729 std::next(MachineBasicBlock::iterator(MI)));730 return VNI->def;731}732 733SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {734 assert(OpenIdx && "openIntv not called before enterIntvAtEnd");735 SlotIndex End = LIS.getMBBEndIdx(&MBB);736 SlotIndex Last = End.getPrevSlot();737 LLVM_DEBUG(dbgs() << " enterIntvAtEnd " << printMBBReference(MBB) << ", "738 << Last);739 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);740 if (!ParentVNI) {741 LLVM_DEBUG(dbgs() << ": not live\n");742 return End;743 }744 SlotIndex LSP = SA.getLastSplitPoint(&MBB);745 if (LSP < Last) {746 // It could be that the use after LSP is a def, and thus the ParentVNI747 // just selected starts at that def. For this case to exist, the def748 // must be part of a tied def/use pair (as otherwise we'd have split749 // distinct live ranges into individual live intervals), and thus we750 // can insert the def into the VNI of the use and the tied def/use751 // pair can live in the resulting interval.752 Last = LSP;753 ParentVNI = Edit->getParent().getVNInfoAt(Last);754 if (!ParentVNI) {755 // undef use --> undef tied def756 LLVM_DEBUG(dbgs() << ": tied use not live\n");757 return End;758 }759 }760 761 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id);762 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,763 SA.getLastSplitPointIter(&MBB));764 RegAssign.insert(VNI->def, End, OpenIdx);765 LLVM_DEBUG(dump());766 return VNI->def;767}768 769/// useIntv - indicate that all instructions in MBB should use OpenLI.770void SplitEditor::useIntv(const MachineBasicBlock &MBB) {771 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));772}773 774void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {775 assert(OpenIdx && "openIntv not called before useIntv");776 LLVM_DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");777 RegAssign.insert(Start, End, OpenIdx);778 LLVM_DEBUG(dump());779}780 781SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {782 assert(OpenIdx && "openIntv not called before leaveIntvAfter");783 LLVM_DEBUG(dbgs() << " leaveIntvAfter " << Idx);784 785 // The interval must be live beyond the instruction at Idx.786 SlotIndex Boundary = Idx.getBoundaryIndex();787 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);788 if (!ParentVNI) {789 LLVM_DEBUG(dbgs() << ": not live\n");790 return Boundary.getNextSlot();791 }792 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');793 MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);794 assert(MI && "No instruction at index");795 796 // In spill mode, make live ranges as short as possible by inserting the copy797 // before MI. This is only possible if that instruction doesn't redefine the798 // value. The inserted COPY is not a kill, and we don't need to recompute799 // the source live range. The spiller also won't try to hoist this copy.800 if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&801 MI->readsVirtualRegister(Edit->getReg())) {802 forceRecompute(0, *ParentVNI);803 defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);804 return Idx;805 }806 807 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),808 std::next(MachineBasicBlock::iterator(MI)));809 return VNI->def;810}811 812SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {813 assert(OpenIdx && "openIntv not called before leaveIntvBefore");814 LLVM_DEBUG(dbgs() << " leaveIntvBefore " << Idx);815 816 // The interval must be live into the instruction at Idx.817 Idx = Idx.getBaseIndex();818 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);819 if (!ParentVNI) {820 LLVM_DEBUG(dbgs() << ": not live\n");821 return Idx.getNextSlot();822 }823 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');824 825 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);826 assert(MI && "No instruction at index");827 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);828 return VNI->def;829}830 831SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {832 assert(OpenIdx && "openIntv not called before leaveIntvAtTop");833 SlotIndex Start = LIS.getMBBStartIdx(&MBB);834 LLVM_DEBUG(dbgs() << " leaveIntvAtTop " << printMBBReference(MBB) << ", "835 << Start);836 837 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);838 if (!ParentVNI) {839 LLVM_DEBUG(dbgs() << ": not live\n");840 return Start;841 }842 843 unsigned RegIdx = 0;844 Register Reg = LIS.getInterval(Edit->get(RegIdx)).reg();845 VNInfo *VNI = defFromParent(RegIdx, ParentVNI, Start, MBB,846 MBB.SkipPHIsLabelsAndDebug(MBB.begin(), Reg));847 RegAssign.insert(Start, VNI->def, OpenIdx);848 LLVM_DEBUG(dump());849 return VNI->def;850}851 852static bool hasTiedUseOf(MachineInstr &MI, Register Reg) {853 return any_of(MI.defs(), [Reg](const MachineOperand &MO) {854 return MO.isReg() && MO.isTied() && MO.getReg() == Reg;855 });856}857 858void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {859 assert(OpenIdx && "openIntv not called before overlapIntv");860 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);861 assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&862 "Parent changes value in extended range");863 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&864 "Range cannot span basic blocks");865 866 // The complement interval will be extended as needed by LICalc.extend().867 if (ParentVNI)868 forceRecompute(0, *ParentVNI);869 870 // If the last use is tied to a def, we can't mark it as live for the871 // interval which includes only the use. That would cause the tied pair872 // to end up in two different intervals.873 if (auto *MI = LIS.getInstructionFromIndex(End))874 if (hasTiedUseOf(*MI, Edit->getReg())) {875 LLVM_DEBUG(dbgs() << "skip overlap due to tied def at end\n");876 return;877 }878 879 LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");880 RegAssign.insert(Start, End, OpenIdx);881 LLVM_DEBUG(dump());882}883 884//===----------------------------------------------------------------------===//885// Spill modes886//===----------------------------------------------------------------------===//887 888void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {889 LiveInterval *LI = &LIS.getInterval(Edit->get(0));890 LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");891 RegAssignMap::iterator AssignI;892 AssignI.setMap(RegAssign);893 894 for (const VNInfo *C : Copies) {895 SlotIndex Def = C->def;896 MachineInstr *MI = LIS.getInstructionFromIndex(Def);897 assert(MI && "No instruction for back-copy");898 899 MachineBasicBlock *MBB = MI->getParent();900 MachineBasicBlock::iterator MBBI(MI);901 bool AtBegin;902 do AtBegin = MBBI == MBB->begin();903 while (!AtBegin && (--MBBI)->isDebugOrPseudoInstr());904 905 LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);906 LIS.removeVRegDefAt(*LI, Def);907 LIS.RemoveMachineInstrFromMaps(*MI);908 MI->eraseFromParent();909 910 // Adjust RegAssign if a register assignment is killed at Def. We want to911 // avoid calculating the live range of the source register if possible.912 AssignI.find(Def.getPrevSlot());913 if (!AssignI.valid() || AssignI.start() >= Def)914 continue;915 // If MI doesn't kill the assigned register, just leave it.916 if (AssignI.stop() != Def)917 continue;918 unsigned RegIdx = AssignI.value();919 // We could hoist back-copy right after another back-copy. As a result920 // MMBI points to copy instruction which is actually dead now.921 // We cannot set its stop to MBBI which will be the same as start and922 // interval does not support that.923 SlotIndex Kill =924 AtBegin ? SlotIndex() : LIS.getInstructionIndex(*MBBI).getRegSlot();925 if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg()) ||926 Kill <= AssignI.start()) {927 LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx928 << '\n');929 forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));930 } else {931 LLVM_DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI);932 AssignI.setStop(Kill);933 }934 }935}936 937MachineBasicBlock*938SplitEditor::findShallowDominator(MachineBasicBlock *MBB,939 MachineBasicBlock *DefMBB) {940 if (MBB == DefMBB)941 return MBB;942 assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");943 944 const MachineLoopInfo &Loops = SA.Loops;945 const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);946 MachineDomTreeNode *DefDomNode = MDT[DefMBB];947 948 // Best candidate so far.949 MachineBasicBlock *BestMBB = MBB;950 unsigned BestDepth = std::numeric_limits<unsigned>::max();951 952 while (true) {953 const MachineLoop *Loop = Loops.getLoopFor(MBB);954 955 // MBB isn't in a loop, it doesn't get any better. All dominators have a956 // higher frequency by definition.957 if (!Loop) {958 LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)959 << " dominates " << printMBBReference(*MBB)960 << " at depth 0\n");961 return MBB;962 }963 964 // We'll never be able to exit the DefLoop.965 if (Loop == DefLoop) {966 LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)967 << " dominates " << printMBBReference(*MBB)968 << " in the same loop\n");969 return MBB;970 }971 972 // Least busy dominator seen so far.973 unsigned Depth = Loop->getLoopDepth();974 if (Depth < BestDepth) {975 BestMBB = MBB;976 BestDepth = Depth;977 LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)978 << " dominates " << printMBBReference(*MBB)979 << " at depth " << Depth << '\n');980 }981 982 // Leave loop by going to the immediate dominator of the loop header.983 // This is a bigger stride than simply walking up the dominator tree.984 MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();985 986 // Too far up the dominator tree?987 if (!IDom || !MDT.dominates(DefDomNode, IDom))988 return BestMBB;989 990 MBB = IDom->getBlock();991 }992}993 994void SplitEditor::computeRedundantBackCopies(995 DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {996 LiveInterval *LI = &LIS.getInterval(Edit->get(0));997 const LiveInterval *Parent = &Edit->getParent();998 SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());999 SmallPtrSet<VNInfo *, 8> DominatedVNIs;1000 1001 // Aggregate VNIs having the same value as ParentVNI.1002 for (VNInfo *VNI : LI->valnos) {1003 if (VNI->isUnused())1004 continue;1005 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);1006 EqualVNs[ParentVNI->id].insert(VNI);1007 }1008 1009 // For VNI aggregation of each ParentVNI, collect dominated, i.e.,1010 // redundant VNIs to BackCopies.1011 for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {1012 const VNInfo *ParentVNI = Parent->getValNumInfo(i);1013 if (!NotToHoistSet.count(ParentVNI->id))1014 continue;1015 SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();1016 SmallPtrSetIterator<VNInfo *> It2 = It1;1017 for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {1018 It2 = It1;1019 for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {1020 if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))1021 continue;1022 1023 MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);1024 MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);1025 if (MBB1 == MBB2) {1026 DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));1027 } else if (MDT.dominates(MBB1, MBB2)) {1028 DominatedVNIs.insert(*It2);1029 } else if (MDT.dominates(MBB2, MBB1)) {1030 DominatedVNIs.insert(*It1);1031 }1032 }1033 }1034 if (!DominatedVNIs.empty()) {1035 forceRecompute(0, *ParentVNI);1036 append_range(BackCopies, DominatedVNIs);1037 DominatedVNIs.clear();1038 }1039 }1040}1041 1042/// For SM_Size mode, find a common dominator for all the back-copies for1043/// the same ParentVNI and hoist the backcopies to the dominator BB.1044/// For SM_Speed mode, if the common dominator is hot and it is not beneficial1045/// to do the hoisting, simply remove the dominated backcopies for the same1046/// ParentVNI.1047void SplitEditor::hoistCopies() {1048 // Get the complement interval, always RegIdx 0.1049 LiveInterval *LI = &LIS.getInterval(Edit->get(0));1050 const LiveInterval *Parent = &Edit->getParent();1051 1052 // Track the nearest common dominator for all back-copies for each ParentVNI,1053 // indexed by ParentVNI->id.1054 using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;1055 SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());1056 // The total cost of all the back-copies for each ParentVNI.1057 SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums());1058 // The ParentVNI->id set for which hoisting back-copies are not beneficial1059 // for Speed.1060 DenseSet<unsigned> NotToHoistSet;1061 1062 // Find the nearest common dominator for parent values with multiple1063 // back-copies. If a single back-copy dominates, put it in DomPair.second.1064 for (VNInfo *VNI : LI->valnos) {1065 if (VNI->isUnused())1066 continue;1067 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);1068 assert(ParentVNI && "Parent not live at complement def");1069 1070 // Don't hoist remats. The complement is probably going to disappear1071 // completely anyway.1072 if (Edit->didRematerialize(ParentVNI))1073 continue;1074 1075 MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);1076 1077 DomPair &Dom = NearestDom[ParentVNI->id];1078 1079 // Keep directly defined parent values. This is either a PHI or an1080 // instruction in the complement range. All other copies of ParentVNI1081 // should be eliminated.1082 if (VNI->def == ParentVNI->def) {1083 LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');1084 Dom = DomPair(ValMBB, VNI->def);1085 continue;1086 }1087 // Skip the singly mapped values. There is nothing to gain from hoisting a1088 // single back-copy.1089 if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {1090 LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');1091 continue;1092 }1093 1094 if (!Dom.first) {1095 // First time we see ParentVNI. VNI dominates itself.1096 Dom = DomPair(ValMBB, VNI->def);1097 } else if (Dom.first == ValMBB) {1098 // Two defs in the same block. Pick the earlier def.1099 if (!Dom.second.isValid() || VNI->def < Dom.second)1100 Dom.second = VNI->def;1101 } else {1102 // Different basic blocks. Check if one dominates.1103 MachineBasicBlock *Near =1104 MDT.findNearestCommonDominator(Dom.first, ValMBB);1105 if (Near == ValMBB)1106 // Def ValMBB dominates.1107 Dom = DomPair(ValMBB, VNI->def);1108 else if (Near != Dom.first)1109 // None dominate. Hoist to common dominator, need new def.1110 Dom = DomPair(Near, SlotIndex());1111 Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);1112 }1113 1114 LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'1115 << VNI->def << " for parent " << ParentVNI->id << '@'1116 << ParentVNI->def << " hoist to "1117 << printMBBReference(*Dom.first) << ' ' << Dom.second1118 << '\n');1119 }1120 1121 // Insert the hoisted copies.1122 for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {1123 DomPair &Dom = NearestDom[i];1124 if (!Dom.first || Dom.second.isValid())1125 continue;1126 // This value needs a hoisted copy inserted at the end of Dom.first.1127 const VNInfo *ParentVNI = Parent->getValNumInfo(i);1128 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);1129 // Get a less loopy dominator than Dom.first.1130 Dom.first = findShallowDominator(Dom.first, DefMBB);1131 if (SpillMode == SM_Speed &&1132 MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {1133 NotToHoistSet.insert(ParentVNI->id);1134 continue;1135 }1136 SlotIndex LSP = SA.getLastSplitPoint(Dom.first);1137 if (LSP <= ParentVNI->def) {1138 NotToHoistSet.insert(ParentVNI->id);1139 continue;1140 }1141 Dom.second = defFromParent(0, ParentVNI, LSP, *Dom.first,1142 SA.getLastSplitPointIter(Dom.first))->def;1143 }1144 1145 // Remove redundant back-copies that are now known to be dominated by another1146 // def with the same value.1147 SmallVector<VNInfo*, 8> BackCopies;1148 for (VNInfo *VNI : LI->valnos) {1149 if (VNI->isUnused())1150 continue;1151 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);1152 const DomPair &Dom = NearestDom[ParentVNI->id];1153 if (!Dom.first || Dom.second == VNI->def ||1154 NotToHoistSet.count(ParentVNI->id))1155 continue;1156 BackCopies.push_back(VNI);1157 forceRecompute(0, *ParentVNI);1158 }1159 1160 // If it is not beneficial to hoist all the BackCopies, simply remove1161 // redundant BackCopies in speed mode.1162 if (SpillMode == SM_Speed && !NotToHoistSet.empty())1163 computeRedundantBackCopies(NotToHoistSet, BackCopies);1164 1165 removeBackCopies(BackCopies);1166}1167 1168/// transferValues - Transfer all possible values to the new live ranges.1169/// Values that were rematerialized are left alone, they need LICalc.extend().1170bool SplitEditor::transferValues() {1171 bool Skipped = false;1172 RegAssignMap::const_iterator AssignI = RegAssign.begin();1173 for (const LiveRange::Segment &S : Edit->getParent()) {1174 LLVM_DEBUG(dbgs() << " blit " << S << ':');1175 VNInfo *ParentVNI = S.valno;1176 // RegAssign has holes where RegIdx 0 should be used.1177 SlotIndex Start = S.start;1178 AssignI.advanceTo(Start);1179 do {1180 unsigned RegIdx;1181 SlotIndex End = S.end;1182 if (!AssignI.valid()) {1183 RegIdx = 0;1184 } else if (AssignI.start() <= Start) {1185 RegIdx = AssignI.value();1186 if (AssignI.stop() < End) {1187 End = AssignI.stop();1188 ++AssignI;1189 }1190 } else {1191 RegIdx = 0;1192 End = std::min(End, AssignI.start());1193 }1194 1195 // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.1196 LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('1197 << printReg(Edit->get(RegIdx)) << ')');1198 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));1199 1200 // Check for a simply defined value that can be blitted directly.1201 ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));1202 if (VNInfo *VNI = VFP.getPointer()) {1203 LLVM_DEBUG(dbgs() << ':' << VNI->id);1204 LI.addSegment(LiveInterval::Segment(Start, End, VNI));1205 Start = End;1206 continue;1207 }1208 1209 // Skip values with forced recomputation.1210 if (VFP.getInt()) {1211 LLVM_DEBUG(dbgs() << "(recalc)");1212 Skipped = true;1213 Start = End;1214 continue;1215 }1216 1217 LiveIntervalCalc &LIC = getLICalc(RegIdx);1218 1219 // This value has multiple defs in RegIdx, but it wasn't rematerialized,1220 // so the live range is accurate. Add live-in blocks in [Start;End) to the1221 // LiveInBlocks.1222 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();1223 SlotIndex BlockStart, BlockEnd;1224 std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);1225 1226 // The first block may be live-in, or it may have its own def.1227 if (Start != BlockStart) {1228 VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));1229 assert(VNI && "Missing def for complex mapped value");1230 LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB));1231 // MBB has its own def. Is it also live-out?1232 if (BlockEnd <= End)1233 LIC.setLiveOutValue(&*MBB, VNI);1234 1235 // Skip to the next block for live-in.1236 ++MBB;1237 BlockStart = BlockEnd;1238 }1239 1240 // Handle the live-in blocks covered by [Start;End).1241 assert(Start <= BlockStart && "Expected live-in block");1242 while (BlockStart < End) {1243 LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB));1244 BlockEnd = LIS.getMBBEndIdx(&*MBB);1245 if (BlockStart == ParentVNI->def) {1246 // This block has the def of a parent PHI, so it isn't live-in.1247 assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");1248 VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));1249 assert(VNI && "Missing def for complex mapped parent PHI");1250 if (End >= BlockEnd)1251 LIC.setLiveOutValue(&*MBB, VNI); // Live-out as well.1252 } else {1253 // This block needs a live-in value. The last block covered may not1254 // be live-out.1255 if (End < BlockEnd)1256 LIC.addLiveInBlock(LI, MDT[&*MBB], End);1257 else {1258 // Live-through, and we don't know the value.1259 LIC.addLiveInBlock(LI, MDT[&*MBB]);1260 LIC.setLiveOutValue(&*MBB, nullptr);1261 }1262 }1263 BlockStart = BlockEnd;1264 ++MBB;1265 }1266 Start = End;1267 } while (Start != S.end);1268 LLVM_DEBUG(dbgs() << '\n');1269 }1270 1271 LICalc[0].calculateValues();1272 if (SpillMode)1273 LICalc[1].calculateValues();1274 1275 return Skipped;1276}1277 1278static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) {1279 const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);1280 if (Seg == nullptr)1281 return true;1282 if (Seg->end != Def.getDeadSlot())1283 return false;1284 // This is a dead PHI. Remove it.1285 LR.removeSegment(*Seg, true);1286 return true;1287}1288 1289void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,1290 LiveRange &LR, LaneBitmask LM,1291 ArrayRef<SlotIndex> Undefs) {1292 for (MachineBasicBlock *P : B.predecessors()) {1293 SlotIndex End = LIS.getMBBEndIdx(P);1294 SlotIndex LastUse = End.getPrevSlot();1295 // The predecessor may not have a live-out value. That is OK, like an1296 // undef PHI operand.1297 const LiveInterval &PLI = Edit->getParent();1298 // Need the cast because the inputs to ?: would otherwise be deemed1299 // "incompatible": SubRange vs LiveInterval.1300 const LiveRange &PSR = !LM.all() ? getSubRangeForMaskExact(LM, PLI)1301 : static_cast<const LiveRange &>(PLI);1302 if (PSR.liveAt(LastUse))1303 LIC.extend(LR, End, /*PhysReg=*/0, Undefs);1304 }1305}1306 1307void SplitEditor::extendPHIKillRanges() {1308 // Extend live ranges to be live-out for successor PHI values.1309 1310 // Visit each PHI def slot in the parent live interval. If the def is dead,1311 // remove it. Otherwise, extend the live interval to reach the end indexes1312 // of all predecessor blocks.1313 1314 const LiveInterval &ParentLI = Edit->getParent();1315 for (const VNInfo *V : ParentLI.valnos) {1316 if (V->isUnused() || !V->isPHIDef())1317 continue;1318 1319 unsigned RegIdx = RegAssign.lookup(V->def);1320 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));1321 LiveIntervalCalc &LIC = getLICalc(RegIdx);1322 MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);1323 if (!removeDeadSegment(V->def, LI))1324 extendPHIRange(B, LIC, LI, LaneBitmask::getAll(), /*Undefs=*/{});1325 }1326 1327 SmallVector<SlotIndex, 4> Undefs;1328 LiveIntervalCalc SubLIC;1329 1330 for (const LiveInterval::SubRange &PS : ParentLI.subranges()) {1331 for (const VNInfo *V : PS.valnos) {1332 if (V->isUnused() || !V->isPHIDef())1333 continue;1334 unsigned RegIdx = RegAssign.lookup(V->def);1335 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));1336 LiveInterval::SubRange &S = getSubRangeForMaskExact(PS.LaneMask, LI);1337 if (removeDeadSegment(V->def, S))1338 continue;1339 1340 MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);1341 SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,1342 &LIS.getVNInfoAllocator());1343 Undefs.clear();1344 LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());1345 extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs);1346 }1347 }1348}1349 1350/// rewriteAssigned - Rewrite all uses of Edit->getReg().1351void SplitEditor::rewriteAssigned(bool ExtendRanges) {1352 struct ExtPoint {1353 ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)1354 : MO(O), RegIdx(R), Next(N) {}1355 1356 MachineOperand MO;1357 unsigned RegIdx;1358 SlotIndex Next;1359 };1360 1361 SmallVector<ExtPoint,4> ExtPoints;1362 1363 for (MachineOperand &MO :1364 llvm::make_early_inc_range(MRI.reg_operands(Edit->getReg()))) {1365 MachineInstr *MI = MO.getParent();1366 // LiveDebugVariables should have handled all DBG_VALUE instructions.1367 if (MI->isDebugValue()) {1368 LLVM_DEBUG(dbgs() << "Zapping " << *MI);1369 MO.setReg(0);1370 continue;1371 }1372 1373 // <undef> operands don't really read the register, so it doesn't matter1374 // which register we choose. When the use operand is tied to a def, we must1375 // use the same register as the def, so just do that always.1376 SlotIndex Idx = LIS.getInstructionIndex(*MI);1377 if (MO.isDef() || MO.isUndef())1378 Idx = Idx.getRegSlot(MO.isEarlyClobber());1379 1380 // Rewrite to the mapped register at Idx.1381 unsigned RegIdx = RegAssign.lookup(Idx);1382 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));1383 MO.setReg(LI.reg());1384 LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI->getParent())1385 << '\t' << Idx << ':' << RegIdx << '\t' << *MI);1386 1387 // Extend liveness to Idx if the instruction reads reg.1388 if (!ExtendRanges || MO.isUndef())1389 continue;1390 1391 // Skip instructions that don't read Reg.1392 if (MO.isDef()) {1393 if (!MO.getSubReg() && !MO.isEarlyClobber())1394 continue;1395 // We may want to extend a live range for a partial redef, or for a use1396 // tied to an early clobber.1397 if (!Edit->getParent().liveAt(Idx.getPrevSlot()))1398 continue;1399 } else {1400 assert(MO.isUse());1401 bool IsEarlyClobber = false;1402 if (MO.isTied()) {1403 // We want to extend a live range into `e` slot rather than `r` slot if1404 // tied-def is early clobber, because the `e` slot already contained1405 // in the live range of early-clobber tied-def operand, give an example1406 // here:1407 // 0 %0 = ...1408 // 16 early-clobber %0 = Op %0 (tied-def 0), ...1409 // 32 ... = Op %01410 // Before extend:1411 // %0 = [0r, 0d) [16e, 32d)1412 // The point we want to extend is 0d to 16e not 16r in this case, but if1413 // we use 16r here we will extend nothing because that already contained1414 // in [16e, 32d).1415 unsigned OpIdx = MO.getOperandNo();1416 unsigned DefOpIdx = MI->findTiedOperandIdx(OpIdx);1417 const MachineOperand &DefOp = MI->getOperand(DefOpIdx);1418 IsEarlyClobber = DefOp.isEarlyClobber();1419 }1420 1421 Idx = Idx.getRegSlot(IsEarlyClobber);1422 }1423 1424 SlotIndex Next = Idx;1425 if (LI.hasSubRanges()) {1426 // We have to delay extending subranges until we have seen all operands1427 // defining the register. This is because a <def,read-undef> operand1428 // will create an "undef" point, and we cannot extend any subranges1429 // until all of them have been accounted for.1430 if (MO.isUse())1431 ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));1432 } else {1433 LiveIntervalCalc &LIC = getLICalc(RegIdx);1434 LIC.extend(LI, Next, 0, ArrayRef<SlotIndex>());1435 }1436 }1437 1438 for (ExtPoint &EP : ExtPoints) {1439 LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));1440 assert(LI.hasSubRanges());1441 1442 LiveIntervalCalc SubLIC;1443 Register Reg = EP.MO.getReg();1444 unsigned Sub = EP.MO.getSubReg();1445 LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)1446 : MRI.getMaxLaneMaskForVReg(Reg);1447 for (LiveInterval::SubRange &S : LI.subranges()) {1448 if ((S.LaneMask & LM).none())1449 continue;1450 // The problem here can be that the new register may have been created1451 // for a partially defined original register. For example:1452 // %0:subreg_hireg<def,read-undef> = ...1453 // ...1454 // %1 = COPY %01455 if (S.empty())1456 continue;1457 SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,1458 &LIS.getVNInfoAllocator());1459 SmallVector<SlotIndex, 4> Undefs;1460 LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());1461 SubLIC.extend(S, EP.Next, 0, Undefs);1462 }1463 }1464 1465 for (Register R : *Edit) {1466 LiveInterval &LI = LIS.getInterval(R);1467 if (!LI.hasSubRanges())1468 continue;1469 LI.clear();1470 LI.removeEmptySubRanges();1471 LIS.constructMainRangeFromSubranges(LI);1472 }1473}1474 1475void SplitEditor::deleteRematVictims() {1476 SmallVector<MachineInstr*, 8> Dead;1477 for (const Register &R : *Edit) {1478 LiveInterval *LI = &LIS.getInterval(R);1479 for (const LiveRange::Segment &S : LI->segments) {1480 // Dead defs end at the dead slot.1481 if (S.end != S.valno->def.getDeadSlot())1482 continue;1483 if (S.valno->isPHIDef())1484 continue;1485 MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);1486 assert(MI && "Missing instruction for dead def");1487 MI->addRegisterDead(LI->reg(), &TRI);1488 1489 if (!MI->allDefsAreDead())1490 continue;1491 1492 LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);1493 Dead.push_back(MI);1494 }1495 }1496 1497 if (Dead.empty())1498 return;1499 1500 Edit->eliminateDeadDefs(Dead, {});1501}1502 1503void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {1504 // Fast-path for common case.1505 if (!ParentVNI.isPHIDef()) {1506 for (unsigned I = 0, E = Edit->size(); I != E; ++I)1507 forceRecompute(I, ParentVNI);1508 return;1509 }1510 1511 // Trace value through phis.1512 ///< whether VNI was/is in worklist.1513 SmallPtrSet<const VNInfo *, 8> Visited = {&ParentVNI};1514 SmallVector<const VNInfo *, 4> WorkList = {&ParentVNI};1515 1516 const LiveInterval &ParentLI = Edit->getParent();1517 const SlotIndexes &Indexes = *LIS.getSlotIndexes();1518 do {1519 const VNInfo &VNI = *WorkList.pop_back_val();1520 for (unsigned I = 0, E = Edit->size(); I != E; ++I)1521 forceRecompute(I, VNI);1522 if (!VNI.isPHIDef())1523 continue;1524 1525 MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def);1526 for (const MachineBasicBlock *Pred : MBB.predecessors()) {1527 SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);1528 VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd);1529 assert(PredVNI && "Value available in PhiVNI predecessor");1530 if (Visited.insert(PredVNI).second)1531 WorkList.push_back(PredVNI);1532 }1533 } while(!WorkList.empty());1534}1535 1536void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {1537 ++NumFinished;1538 1539 // At this point, the live intervals in Edit contain VNInfos corresponding to1540 // the inserted copies.1541 1542 // Add the original defs from the parent interval.1543 for (const VNInfo *ParentVNI : Edit->getParent().valnos) {1544 if (ParentVNI->isUnused())1545 continue;1546 unsigned RegIdx = RegAssign.lookup(ParentVNI->def);1547 defValue(RegIdx, ParentVNI, ParentVNI->def, true);1548 1549 // Force rematted values to be recomputed everywhere.1550 // The new live ranges may be truncated.1551 if (Edit->didRematerialize(ParentVNI))1552 forceRecomputeVNI(*ParentVNI);1553 }1554 1555 // Hoist back-copies to the complement interval when in spill mode.1556 switch (SpillMode) {1557 case SM_Partition:1558 // Leave all back-copies as is.1559 break;1560 case SM_Size:1561 case SM_Speed:1562 // hoistCopies will behave differently between size and speed.1563 hoistCopies();1564 }1565 1566 // Transfer the simply mapped values, check if any are skipped.1567 bool Skipped = transferValues();1568 1569 // Rewrite virtual registers, possibly extending ranges.1570 rewriteAssigned(Skipped);1571 1572 if (Skipped)1573 extendPHIKillRanges();1574 else1575 ++NumSimple;1576 1577 // Delete defs that were rematted everywhere.1578 if (Skipped)1579 deleteRematVictims();1580 1581 // Get rid of unused values and set phi-kill flags.1582 for (Register Reg : *Edit) {1583 LiveInterval &LI = LIS.getInterval(Reg);1584 LI.removeEmptySubRanges();1585 LI.RenumberValues();1586 }1587 1588 // Provide a reverse mapping from original indices to Edit ranges.1589 if (LRMap) {1590 auto Seq = llvm::seq<unsigned>(0, Edit->size());1591 LRMap->assign(Seq.begin(), Seq.end());1592 }1593 1594 // Now check if any registers were separated into multiple components.1595 ConnectedVNInfoEqClasses ConEQ(LIS);1596 for (unsigned i = 0, e = Edit->size(); i != e; ++i) {1597 // Don't use iterators, they are invalidated by create() below.1598 Register VReg = Edit->get(i);1599 LiveInterval &LI = LIS.getInterval(VReg);1600 SmallVector<LiveInterval*, 8> SplitLIs;1601 LIS.splitSeparateComponents(LI, SplitLIs);1602 Register Original = VRM.getOriginal(VReg);1603 for (LiveInterval *SplitLI : SplitLIs)1604 VRM.setIsSplitFromReg(SplitLI->reg(), Original);1605 1606 // The new intervals all map back to i.1607 if (LRMap)1608 LRMap->resize(Edit->size(), i);1609 }1610 1611 // Calculate spill weight and allocation hints for new intervals.1612 Edit->calculateRegClassAndHint(VRM.getMachineFunction(), VRAI);1613 1614 assert(!LRMap || LRMap->size() == Edit->size());1615}1616 1617//===----------------------------------------------------------------------===//1618// Single Block Splitting1619//===----------------------------------------------------------------------===//1620 1621bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI,1622 bool SingleInstrs) const {1623 // Always split for multiple instructions.1624 if (!BI.isOneInstr())1625 return true;1626 // Don't split for single instructions unless explicitly requested.1627 if (!SingleInstrs)1628 return false;1629 // Splitting a live-through range always makes progress.1630 if (BI.LiveIn && BI.LiveOut)1631 return true;1632 // No point in isolating a copy. It has no register class constraints.1633 MachineInstr *MI = LIS.getInstructionFromIndex(BI.FirstInstr);1634 bool copyLike = TII.isCopyInstr(*MI) || MI->isSubregToReg();1635 if (copyLike)1636 return false;1637 // Finally, don't isolate an end point that was created by earlier splits.1638 return isOriginalEndpoint(BI.FirstInstr);1639}1640 1641void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) {1642 openIntv();1643 SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB);1644 SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,1645 LastSplitPoint));1646 if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {1647 useIntv(SegStart, leaveIntvAfter(BI.LastInstr));1648 } else {1649 // The last use is after the last valid split point.1650 SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);1651 useIntv(SegStart, SegStop);1652 overlapIntv(SegStop, BI.LastInstr);1653 }1654}1655 1656//===----------------------------------------------------------------------===//1657// Global Live Range Splitting Support1658//===----------------------------------------------------------------------===//1659 1660// These methods support a method of global live range splitting that uses a1661// global algorithm to decide intervals for CFG edges. They will insert split1662// points and color intervals in basic blocks while avoiding interference.1663//1664// Note that splitSingleBlock is also useful for blocks where both CFG edges1665// are on the stack.1666 1667void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,1668 unsigned IntvIn, SlotIndex LeaveBefore,1669 unsigned IntvOut, SlotIndex EnterAfter){1670 SlotIndex Start, Stop;1671 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);1672 1673 LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop1674 << ") intf " << LeaveBefore << '-' << EnterAfter1675 << ", live-through " << IntvIn << " -> " << IntvOut);1676 1677 assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");1678 1679 assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");1680 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");1681 assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");1682 1683 MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);1684 1685 if (!IntvOut) {1686 LLVM_DEBUG(dbgs() << ", spill on entry.\n");1687 //1688 // <<<<<<<<< Possible LeaveBefore interference.1689 // |-----------| Live through.1690 // -____________ Spill on entry.1691 //1692 selectIntv(IntvIn);1693 SlotIndex Idx = leaveIntvAtTop(*MBB);1694 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");1695 (void)Idx;1696 return;1697 }1698 1699 if (!IntvIn) {1700 LLVM_DEBUG(dbgs() << ", reload on exit.\n");1701 //1702 // >>>>>>> Possible EnterAfter interference.1703 // |-----------| Live through.1704 // ___________-- Reload on exit.1705 //1706 selectIntv(IntvOut);1707 SlotIndex Idx = enterIntvAtEnd(*MBB);1708 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");1709 (void)Idx;1710 return;1711 }1712 1713 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {1714 LLVM_DEBUG(dbgs() << ", straight through.\n");1715 //1716 // |-----------| Live through.1717 // ------------- Straight through, same intv, no interference.1718 //1719 selectIntv(IntvOut);1720 useIntv(Start, Stop);1721 return;1722 }1723 1724 // We cannot legally insert splits after LSP.1725 SlotIndex LSP = SA.getLastSplitPoint(MBBNum);1726 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");1727 1728 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||1729 LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {1730 LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");1731 //1732 // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference.1733 // |-----------| Live through.1734 // ------======= Switch intervals between interference.1735 //1736 selectIntv(IntvOut);1737 SlotIndex Idx;1738 if (LeaveBefore && LeaveBefore < LSP) {1739 Idx = enterIntvBefore(LeaveBefore);1740 useIntv(Idx, Stop);1741 } else {1742 Idx = enterIntvAtEnd(*MBB);1743 }1744 selectIntv(IntvIn);1745 useIntv(Start, Idx);1746 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");1747 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");1748 return;1749 }1750 1751 LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");1752 //1753 // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference.1754 // |-----------| Live through.1755 // ==---------== Switch intervals before/after interference.1756 //1757 assert(LeaveBefore <= EnterAfter && "Missed case");1758 1759 selectIntv(IntvOut);1760 SlotIndex Idx = enterIntvAfter(EnterAfter);1761 useIntv(Idx, Stop);1762 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");1763 1764 selectIntv(IntvIn);1765 Idx = leaveIntvBefore(LeaveBefore);1766 useIntv(Start, Idx);1767 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");1768}1769 1770void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,1771 unsigned IntvIn, SlotIndex LeaveBefore) {1772 SlotIndex Start, Stop;1773 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);1774 1775 LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'1776 << Stop << "), uses " << BI.FirstInstr << '-'1777 << BI.LastInstr << ", reg-in " << IntvIn1778 << ", leave before " << LeaveBefore1779 << (BI.LiveOut ? ", stack-out" : ", killed in block"));1780 1781 assert(IntvIn && "Must have register in");1782 assert(BI.LiveIn && "Must be live-in");1783 assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");1784 1785 if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {1786 LLVM_DEBUG(dbgs() << " before interference.\n");1787 //1788 // <<< Interference after kill.1789 // |---o---x | Killed in block.1790 // ========= Use IntvIn everywhere.1791 //1792 selectIntv(IntvIn);1793 useIntv(Start, BI.LastInstr);1794 return;1795 }1796 1797 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB);1798 1799 if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {1800 //1801 // <<< Possible interference after last use.1802 // |---o---o---| Live-out on stack.1803 // =========____ Leave IntvIn after last use.1804 //1805 // < Interference after last use.1806 // |---o---o--o| Live-out on stack, late last use.1807 // ============ Copy to stack after LSP, overlap IntvIn.1808 // \_____ Stack interval is live-out.1809 //1810 if (BI.LastInstr < LSP) {1811 LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");1812 selectIntv(IntvIn);1813 SlotIndex Idx = leaveIntvAfter(BI.LastInstr);1814 useIntv(Start, Idx);1815 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");1816 } else {1817 LLVM_DEBUG(dbgs() << ", spill before last split point.\n");1818 selectIntv(IntvIn);1819 SlotIndex Idx = leaveIntvBefore(LSP);1820 overlapIntv(Idx, BI.LastInstr);1821 useIntv(Start, Idx);1822 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");1823 }1824 return;1825 }1826 1827 // The interference is overlapping somewhere we wanted to use IntvIn. That1828 // means we need to create a local interval that can be allocated a1829 // different register.1830 unsigned LocalIntv = openIntv();1831 (void)LocalIntv;1832 LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");1833 1834 if (!BI.LiveOut || BI.LastInstr < LSP) {1835 //1836 // <<<<<<< Interference overlapping uses.1837 // |---o---o---| Live-out on stack.1838 // =====----____ Leave IntvIn before interference, then spill.1839 //1840 SlotIndex To = leaveIntvAfter(BI.LastInstr);1841 SlotIndex From = enterIntvBefore(LeaveBefore);1842 useIntv(From, To);1843 selectIntv(IntvIn);1844 useIntv(Start, From);1845 assert((!LeaveBefore || From <= LeaveBefore) && "Interference");1846 return;1847 }1848 1849 // <<<<<<< Interference overlapping uses.1850 // |---o---o--o| Live-out on stack, late last use.1851 // =====------- Copy to stack before LSP, overlap LocalIntv.1852 // \_____ Stack interval is live-out.1853 //1854 SlotIndex To = leaveIntvBefore(LSP);1855 overlapIntv(To, BI.LastInstr);1856 SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));1857 useIntv(From, To);1858 selectIntv(IntvIn);1859 useIntv(Start, From);1860 assert((!LeaveBefore || From <= LeaveBefore) && "Interference");1861}1862 1863void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,1864 unsigned IntvOut, SlotIndex EnterAfter) {1865 SlotIndex Start, Stop;1866 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);1867 1868 LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'1869 << Stop << "), uses " << BI.FirstInstr << '-'1870 << BI.LastInstr << ", reg-out " << IntvOut1871 << ", enter after " << EnterAfter1872 << (BI.LiveIn ? ", stack-in" : ", defined in block"));1873 1874 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB);1875 1876 assert(IntvOut && "Must have register out");1877 assert(BI.LiveOut && "Must be live-out");1878 assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");1879 1880 if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {1881 LLVM_DEBUG(dbgs() << " after interference.\n");1882 //1883 // >>>> Interference before def.1884 // | o---o---| Defined in block.1885 // ========= Use IntvOut everywhere.1886 //1887 selectIntv(IntvOut);1888 useIntv(BI.FirstInstr, Stop);1889 return;1890 }1891 1892 if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {1893 LLVM_DEBUG(dbgs() << ", reload after interference.\n");1894 //1895 // >>>> Interference before def.1896 // |---o---o---| Live-through, stack-in.1897 // ____========= Enter IntvOut before first use.1898 //1899 selectIntv(IntvOut);1900 SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));1901 useIntv(Idx, Stop);1902 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");1903 return;1904 }1905 1906 // The interference is overlapping somewhere we wanted to use IntvOut. That1907 // means we need to create a local interval that can be allocated a1908 // different register.1909 LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");1910 //1911 // >>>>>>> Interference overlapping uses.1912 // |---o---o---| Live-through, stack-in.1913 // ____---====== Create local interval for interference range.1914 //1915 selectIntv(IntvOut);1916 SlotIndex Idx = enterIntvAfter(EnterAfter);1917 useIntv(Idx, Stop);1918 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");1919 1920 openIntv();1921 SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));1922 useIntv(From, Idx);1923}1924 1925void SplitAnalysis::BlockInfo::print(raw_ostream &OS) const {1926 OS << "{" << printMBBReference(*MBB) << ", "1927 << "uses " << FirstInstr << " to " << LastInstr << ", "1928 << "1st def " << FirstDef << ", "1929 << (LiveIn ? "live in" : "dead in") << ", "1930 << (LiveOut ? "live out" : "dead out") << "}";1931}1932 1933void SplitAnalysis::BlockInfo::dump() const {1934 print(dbgs());1935 dbgs() << "\n";1936}1937