From ffbc9c7f3bd9cdb5696c9bd3e3c0b9b8b7128aaa Mon Sep 17 00:00:00 2001 From: Wei Mi Date: Mon, 4 Apr 2016 16:42:40 +0000 Subject: Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265309 --- llvm/lib/CodeGen/LiveRangeEdit.cpp | 63 ++++++++++++++++++++++++++------------ 1 file changed, 43 insertions(+), 20 deletions(-) (limited to 'llvm/lib/CodeGen/LiveRangeEdit.cpp') diff --git a/llvm/lib/CodeGen/LiveRangeEdit.cpp b/llvm/lib/CodeGen/LiveRangeEdit.cpp index 72eafcd0792..5610c5afa0d 100644 --- a/llvm/lib/CodeGen/LiveRangeEdit.cpp +++ b/llvm/lib/CodeGen/LiveRangeEdit.cpp @@ -63,10 +63,13 @@ void LiveRangeEdit::scanRemattable(AliasAnalysis *aa) { 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; } @@ -113,24 +116,18 @@ bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI, return true; } -bool LiveRangeEdit::canRematerializeAt(Remat &RM, - SlotIndex UseIdx, - bool cheapAsAMove) { +bool LiveRangeEdit::canRematerializeAt(Remat &RM, VNInfo *OrigVNI, + SlotIndex UseIdx, bool cheapAsAMove) { assert(ScannedRemattable && "Call anyRematerializable first"); // Use scanRemattable info. - if (!Remattable.count(RM.ParentVNI)) + if (!Remattable.count(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 +258,15 @@ void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) { // 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 +320,24 @@ void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) { } 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 +351,9 @@ void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) { } } -void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl &Dead, - ArrayRef RegsBeingSpilled) { +void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl &Dead, + ArrayRef RegsBeingSpilled, + bool NoSplit) { ToShrinkSet ToShrink; for (;;) { @@ -355,6 +375,9 @@ void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl &Dead, 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 -- cgit v1.2.3