Index: include/llvm/CodeGen/LiveRangeEdit.h =================================================================== --- include/llvm/CodeGen/LiveRangeEdit.h +++ include/llvm/CodeGen/LiveRangeEdit.h @@ -60,6 +60,7 @@ private: LiveInterval *Parent; SmallVectorImpl &NewRegs; + SmallPtrSet *DeadRemats; MachineRegisterInfo &MRI; LiveIntervals &LIS; VirtRegMap *VRM; @@ -111,18 +112,21 @@ /// @param parent The register being spilled or split. /// @param newRegs List to receive any new registers created. This needn't be /// empty initially, any existing registers are ignored. + /// @param deadRemats The collection of all the instructions defining an + /// original reg and are dead after remat. /// @param MF The MachineFunction the live range edit is taking place in. /// @param lis The collection of all live intervals in this function. /// @param vrm Map of virtual registers to physical registers for this /// function. If NULL, no virtual register map updates will /// be done. This could be the case if called before Regalloc. LiveRangeEdit(LiveInterval *parent, SmallVectorImpl &newRegs, + SmallPtrSet *deadRemats, MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm, Delegate *delegate = nullptr) - : Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis), - VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), - TheDelegate(delegate), FirstNew(newRegs.size()), - ScannedRemattable(false) { + : Parent(parent), NewRegs(newRegs), DeadRemats(deadRemats), + MRI(MF.getRegInfo()), LIS(lis), VRM(vrm), + TII(*MF.getSubtarget().getInstrInfo()), TheDelegate(delegate), + FirstNew(newRegs.size()), ScannedRemattable(false) { MRI.setDelegate(this); } @@ -141,6 +145,7 @@ unsigned size() const { return NewRegs.size()-FirstNew; } bool empty() const { return size() == 0; } unsigned get(unsigned idx) const { return NewRegs[idx+FirstNew]; } + void pop_back() { NewRegs.pop_back(); } ArrayRef regs() const { return makeArrayRef(NewRegs).slice(FirstNew); @@ -175,8 +180,11 @@ /// Remat - Information needed to rematerialize at a specific location. struct Remat { VNInfo *ParentVNI; // parent_'s value at the remat location. - MachineInstr *OrigMI; // Instruction defining ParentVNI. - explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI), OrigMI(nullptr) {} + VNInfo *OrigVNI; // ParentVNI.def may be a copy only. OrigVNI.def + // contains the real expr for remat. + MachineInstr *OrigMI; // Instruction defining OrigVNI. + explicit Remat(VNInfo *ParentVNI, VNInfo *OrigVNI) + : ParentVNI(ParentVNI), OrigVNI(OrigVNI), OrigMI(nullptr) {} }; /// canRematerializeAt - Determine if ParentVNI can be rematerialized at @@ -208,6 +216,12 @@ return Rematted.count(ParentVNI); } + void markDeadRemat(MachineInstr *inst) { + // For regallocs other than Greedy, DeadRemats is nullptr for now. + if (DeadRemats) + DeadRemats->insert(inst); + } + /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try /// to erase it from LIS. void eraseVirtReg(unsigned Reg); @@ -218,8 +232,11 @@ /// RegsBeingSpilled lists registers currently being spilled by the register /// allocator. These registers should not be split into new intervals /// as currently those new intervals are not guaranteed to spill. - void eliminateDeadDefs(SmallVectorImpl &Dead, - ArrayRef RegsBeingSpilled = None); + /// NoSplit indicates it is used after the iterations of selectOrSplit and + /// registers should not be split into new intervals. + void eliminateDeadDefs(SmallVectorImpl &Dead, + ArrayRef RegsBeingSpilled = None, + bool NoSplit = false); /// calculateRegClassAndHint - Recompute register class and hint for each new /// register. Index: lib/CodeGen/InlineSpiller.cpp =================================================================== --- lib/CodeGen/InlineSpiller.cpp +++ lib/CodeGen/InlineSpiller.cpp @@ -881,11 +881,11 @@ if (SnippetCopies.count(MI)) return false; - // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy. - LiveRangeEdit::Remat RM(ParentVNI); - SibValueMap::const_iterator SibI = SibValues.find(ParentVNI); - if (SibI != SibValues.end()) - RM.OrigMI = SibI->second.DefMI; + LiveInterval &OrigLI = LIS.getInterval(Original); + VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx); + LiveRangeEdit::Remat RM(ParentVNI, OrigVNI); + RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); + if (!Edit->canRematerializeAt(RM, UseIdx, false)) { markValueUsed(&VirtReg, ParentVNI); DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI); Index: lib/CodeGen/LiveRangeEdit.cpp =================================================================== --- lib/CodeGen/LiveRangeEdit.cpp +++ lib/CodeGen/LiveRangeEdit.cpp @@ -63,10 +63,13 @@ for (VNInfo *VNI : getParent().valnos) { if (VNI->isUnused()) continue; - MachineInstr *DefMI = LIS.getInstructionFromIndex(VNI->def); + unsigned Original = VRM->getOriginal(getReg()); + LiveInterval &OrigLI = LIS.getInterval(Original); + VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def); + MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def); if (!DefMI) continue; - checkRematerializable(VNI, DefMI, aa); + checkRematerializable(OrigVNI, DefMI, aa); } ScannedRemattable = true; } @@ -119,18 +122,13 @@ assert(ScannedRemattable && "Call anyRematerializable first"); // Use scanRemattable info. - if (!Remattable.count(RM.ParentVNI)) + if (!Remattable.count(RM.OrigVNI)) return false; // No defining instruction provided. SlotIndex DefIdx; - if (RM.OrigMI) - DefIdx = LIS.getInstructionIndex(RM.OrigMI); - else { - DefIdx = RM.ParentVNI->def; - RM.OrigMI = LIS.getInstructionFromIndex(DefIdx); - assert(RM.OrigMI && "No defining instruction for remattable value"); - } + assert(RM.OrigMI && "No defining instruction for remattable value"); + DefIdx = LIS.getInstructionIndex(RM.OrigMI); // If only cheap remats were requested, bail out early. if (cheapAsAMove && !TII.isAsCheapAsAMove(RM.OrigMI)) @@ -261,6 +259,15 @@ // Collect virtual registers to be erased after MI is gone. SmallVector RegsToErase; bool ReadsPhysRegs = false; + bool isOrigDef = false; + unsigned Dest; + if (VRM && MI->getOperand(0).isReg()) { + Dest = MI->getOperand(0).getReg(); + unsigned Original = VRM->getOriginal(Dest); + LiveInterval &OrigLI = LIS.getInterval(Original); + VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx); + isOrigDef = SlotIndex::isSameInstr(OrigVNI->def, Idx); + } // Check for live intervals that may shrink for (MachineInstr::mop_iterator MOI = MI->operands_begin(), @@ -314,11 +321,24 @@ } DEBUG(dbgs() << "Converted physregs to:\t" << *MI); } else { - if (TheDelegate) - TheDelegate->LRE_WillEraseInstruction(MI); - LIS.RemoveMachineInstrFromMaps(MI); - MI->eraseFromParent(); - ++NumDCEDeleted; + // If the dest of MI is an original reg, don't delete the inst. Replace + // the dest with a new reg, keep the inst for remat of other siblings. + // The inst is saved in LiveRangeEdit::DeadRemats and will be deleted + // after all the allocations of the func are done. + if (isOrigDef) { + unsigned NewDest = createFrom(Dest); + pop_back(); + markDeadRemat(MI); + const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); + MI->substituteRegister(Dest, NewDest, 0, TRI); + MI->getOperand(0).setIsDead(false); + } else { + if (TheDelegate) + TheDelegate->LRE_WillEraseInstruction(MI); + LIS.RemoveMachineInstrFromMaps(MI); + MI->eraseFromParent(); + ++NumDCEDeleted; + } } // Erase any virtregs that are now empty and unused. There may be @@ -332,8 +352,9 @@ } } -void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl &Dead, - ArrayRef RegsBeingSpilled) { +void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl &Dead, + ArrayRef RegsBeingSpilled, + bool NoSplit) { ToShrinkSet ToShrink; for (;;) { @@ -355,6 +376,9 @@ if (!LIS.shrinkToUses(LI, &Dead)) continue; + if (NoSplit) + continue; + // Don't create new intervals for a register being spilled. // The new intervals would have to be spilled anyway so its not worth it. // Also they currently aren't spilled so creating them and not spilling Index: lib/CodeGen/RegAllocBase.h =================================================================== --- lib/CodeGen/RegAllocBase.h +++ lib/CodeGen/RegAllocBase.h @@ -65,6 +65,12 @@ LiveRegMatrix *Matrix; RegisterClassInfo RegClassInfo; + /// Inst which is a def of an original reg and whose defs are already all + /// dead after remat is saved in DeadRemats. The deletion of such inst is + /// postponed till all the allocations are done, so its remat expr is + /// always available for the remat of all the siblings of the original reg. + SmallPtrSet DeadRemats; + RegAllocBase() : TRI(nullptr), MRI(nullptr), VRM(nullptr), LIS(nullptr), Matrix(nullptr) {} @@ -77,6 +83,9 @@ // physical register assignments. void allocatePhysRegs(); + // Remove dead defs because of rematerialization. + void eliminateDeadRemats(); + // Get a temporary reference to a Spiller instance. virtual Spiller &spiller() = 0; Index: lib/CodeGen/RegAllocBase.cpp =================================================================== --- lib/CodeGen/RegAllocBase.cpp +++ lib/CodeGen/RegAllocBase.cpp @@ -153,3 +153,11 @@ } } } + +void RegAllocBase::eliminateDeadRemats() { + for (auto ent : DeadRemats) { + LIS->RemoveMachineInstrFromMaps(ent); + ent->eraseFromParent(); + } + DeadRemats.clear(); +} Index: lib/CodeGen/RegAllocBasic.cpp =================================================================== --- lib/CodeGen/RegAllocBasic.cpp +++ lib/CodeGen/RegAllocBasic.cpp @@ -199,7 +199,7 @@ Matrix->unassign(Spill); // Spill the extracted interval. - LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM); + LiveRangeEdit LRE(&Spill, SplitVRegs, &DeadRemats, *MF, *LIS, VRM); spiller().spill(LRE); } return true; @@ -258,7 +258,7 @@ DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); if (!VirtReg.isSpillable()) return ~0u; - LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM); + LiveRangeEdit LRE(&VirtReg, SplitVRegs, &DeadRemats, *MF, *LIS, VRM); spiller().spill(LRE); // The live virtual register requesting allocation was spilled, so tell @@ -283,6 +283,7 @@ SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); allocatePhysRegs(); + eliminateDeadRemats(); // Diagnostic output before rewriting DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); Index: lib/CodeGen/RegAllocGreedy.cpp =================================================================== --- lib/CodeGen/RegAllocGreedy.cpp +++ lib/CodeGen/RegAllocGreedy.cpp @@ -1457,7 +1457,7 @@ SmallVectorImpl &NewVRegs) { SmallVector UsedCands; // Prepare split editor. - LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); + LiveRangeEdit LREdit(&VirtReg, NewVRegs, &DeadRemats, *MF, *LIS, VRM, this); SE->reset(LREdit, SplitSpillMode); // Assign all edge bundles to the preferred candidate, or NoCand. @@ -1505,7 +1505,7 @@ assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); unsigned Reg = VirtReg.reg; bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); - LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); + LiveRangeEdit LREdit(&VirtReg, NewVRegs, &DeadRemats, *MF, *LIS, VRM, this); SE->reset(LREdit, SplitSpillMode); ArrayRef UseBlocks = SA->getUseBlocks(); for (unsigned i = 0; i != UseBlocks.size(); ++i) { @@ -1577,7 +1577,7 @@ // Always enable split spill mode, since we're effectively spilling to a // register. - LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); + LiveRangeEdit LREdit(&VirtReg, NewVRegs, &DeadRemats, *MF, *LIS, VRM, this); SE->reset(LREdit, SplitEditor::SM_Size); ArrayRef Uses = SA->getUseSlots(); @@ -1900,7 +1900,7 @@ << '-' << Uses[BestAfter] << ", " << BestDiff << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); - LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); + LiveRangeEdit LREdit(&VirtReg, NewVRegs, &DeadRemats, *MF, *LIS, VRM, this); SE->reset(LREdit); SE->openIntv(); @@ -2543,7 +2543,7 @@ NewVRegs.push_back(VirtReg.reg); } else { NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); - LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); + LiveRangeEdit LRE(&VirtReg, NewVRegs, &DeadRemats, *MF, *LIS, VRM, this); spiller().spill(LRE); setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); @@ -2601,6 +2601,7 @@ allocatePhysRegs(); tryHintsRecoloring(); + eliminateDeadRemats(); releaseMemory(); return true; } Index: lib/CodeGen/RegAllocPBQP.cpp =================================================================== --- lib/CodeGen/RegAllocPBQP.cpp +++ lib/CodeGen/RegAllocPBQP.cpp @@ -123,6 +123,12 @@ RegSet VRegsToAlloc, EmptyIntervalVRegs; + /// Inst which is a def of an original reg and whose defs are already all + /// dead after remat is saved in DeadRemats. The deletion of such inst is + /// postponed till all the allocations are done, so its remat expr is + /// always available for the remat of all the siblings of the original reg. + SmallPtrSet DeadRemats; + /// \brief Finds the initial set of vreg intervals to allocate. void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS); @@ -146,6 +152,8 @@ void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM) const; + /// Remove dead defs because of rematerialization. + void eliminateDeadRemats(LiveIntervals &LIS); }; char RegAllocPBQP::ID = 0; @@ -631,7 +639,8 @@ VirtRegMap &VRM, Spiller &VRegSpiller) { VRegsToAlloc.erase(VReg); - LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM); + LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, &DeadRemats, MF, LIS, + &VRM); VRegSpiller.spill(LRE); const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); @@ -713,6 +722,14 @@ } } +void RegAllocPBQP::eliminateDeadRemats(LiveIntervals &LIS) { + for (auto ent : DeadRemats) { + LIS.RemoveMachineInstrFromMaps(ent); + ent->eraseFromParent(); + } + DeadRemats.clear(); +} + static inline float normalizePBQPSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr) { // All intervals have a spill weight that is mostly proportional to the number @@ -798,6 +815,7 @@ // Finalise allocation, allocate empty ranges. finalizeAlloc(MF, LIS, VRM); + eliminateDeadRemats(LIS); VRegsToAlloc.clear(); EmptyIntervalVRegs.clear(); Index: lib/CodeGen/RegisterCoalescer.cpp =================================================================== --- lib/CodeGen/RegisterCoalescer.cpp +++ lib/CodeGen/RegisterCoalescer.cpp @@ -449,8 +449,8 @@ void RegisterCoalescer::eliminateDeadDefs() { SmallVector NewRegs; - LiveRangeEdit(nullptr, NewRegs, *MF, *LIS, - nullptr, this).eliminateDeadDefs(DeadDefs); + LiveRangeEdit(nullptr, NewRegs, nullptr, *MF, *LIS, nullptr, this) + .eliminateDeadDefs(DeadDefs); } void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { Index: lib/CodeGen/SplitKit.cpp =================================================================== --- lib/CodeGen/SplitKit.cpp +++ lib/CodeGen/SplitKit.cpp @@ -430,7 +430,12 @@ bool Late = RegIdx != 0; // Attempt cheap-as-a-copy rematerialization. - LiveRangeEdit::Remat RM(ParentVNI); + unsigned Original = VRM.getOriginal(Edit->get(RegIdx)); + LiveInterval &OrigLI = LIS.getInterval(Original); + VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx); + LiveRangeEdit::Remat RM(ParentVNI, OrigVNI); + RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); + if (Edit->canRematerializeAt(RM, UseIdx, true)) { Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late); ++NumRemats; @@ -1003,6 +1008,8 @@ // Dead defs end at the dead slot. if (S.end != S.valno->def.getDeadSlot()) continue; + if (S.valno->isPHIDef()) + continue; MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def); assert(MI && "Missing instruction for dead def"); MI->addRegisterDead(LI->reg, &TRI);