Index: include/llvm/CodeGen/VirtRegMap.h =================================================================== --- include/llvm/CodeGen/VirtRegMap.h +++ include/llvm/CodeGen/VirtRegMap.h @@ -20,6 +20,7 @@ #include "llvm/ADT/IndexedMap.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/Target/TargetRegisterInfo.h" +#include namespace llvm { class MachineInstr; @@ -60,6 +61,10 @@ /// mapping. IndexedMap Virt2SplitMap; + /// Virt2SibingsMap - This is original register to a set containing all + /// its siblings mapping. + DenseMap> Virt2SiblingsMap; + /// createSpillSlot - Allocate a spill slot for RC from MFI. unsigned createSpillSlot(const TargetRegisterClass *RC); @@ -144,6 +149,21 @@ return Virt2SplitMap[virtReg]; } + /// @brief records Sibling is a sibling register generated from OrigReg. + void setIsSiblingsOfReg(unsigned OrigReg, unsigned Sibling) { + bool inserted; + DenseMap>::iterator It = + Virt2SiblingsMap.find(OrigReg); + if (It == Virt2SiblingsMap.end()) + std::tie(It, inserted) = Virt2SiblingsMap.insert( + std::make_pair(OrigReg, std::set())); + It->second.insert(Sibling); + } + + std::set &getSiblings(unsigned OrigReg) { + return Virt2SiblingsMap[OrigReg]; + } + /// getOriginal - Return the original virtual register that VirtReg descends /// from through splitting. /// A register that was not created by splitting is its own original. Index: lib/CodeGen/InlineSpiller.cpp =================================================================== --- lib/CodeGen/InlineSpiller.cpp +++ lib/CodeGen/InlineSpiller.cpp @@ -132,6 +132,13 @@ typedef DenseMap SibValueMap; SibValueMap SibValues; + typedef DenseMap, std::set> + MergableSpillsMap; + MergableSpillsMap MergableSpills; + + typedef DenseMap, std::set> + EqualVNsMap; + // Dead defs generated during spilling. SmallVector DeadDefs; @@ -151,6 +158,16 @@ void spill(LiveRangeEdit &) override; + void addToMergableSpills(MachineInstr *Spill); + void rmFromMergableSpills(MachineInstr *Spill); + bool isSpillCandBB(unsigned OrigReg, VNInfo *OrigVNI, MachineBasicBlock *BB, + unsigned &LiveReg); + void runHoistSpills( + unsigned OrigReg, VNInfo *OrigVNI, std::set &Spills, + std::set &SpillsToRm, + std::set> &SpillsToIns); + void hoistAllSpills() override; + private: bool isSnippet(const LiveInterval &SnipLI); void collectRegsToSpill(); @@ -809,6 +826,7 @@ DeadDefs.push_back(MI); ++NumSpillsRemoved; --NumSpills; + rmFromMergableSpills(MI); } } } while (!WorkList.empty()); @@ -1023,6 +1041,9 @@ if (InstrReg != Reg || FI != StackSlot) return false; + if (!IsLoad) + rmFromMergableSpills(MI); + DEBUG(dbgs() << "Coalescing stack access: " << *MI); LIS.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -1173,9 +1194,10 @@ if (!WasCopy) ++NumFolded; - else if (Ops.front().second == 0) + else if (Ops.front().second == 0) { ++NumSpills; - else + addToMergableSpills(FoldMI); + } else ++NumReloads; return true; } @@ -1210,6 +1232,7 @@ DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS, "spill")); ++NumSpills; + addToMergableSpills(std::next(MI)); } /// spillAroundUses - insert spill code around each use of Reg. @@ -1387,7 +1410,6 @@ assert(DeadDefs.empty() && "Previous spill didn't remove dead defs"); collectRegsToSpill(); - analyzeSiblingValues(); reMaterializeAll(); // Remat may handle everything. @@ -1396,3 +1418,292 @@ Edit->calculateRegClassAndHint(MF, Loops, MBFI); } + +void InlineSpiller::addToMergableSpills(MachineInstr *Spill) { + SlotIndex Idx = LIS.getInstructionIndex(Spill); + VNInfo *OrigVNI = LIS.getInterval(Original).getVNInfoAt(Idx.getRegSlot()); + bool Inserted; + std::pair MIdx = std::make_pair(StackSlot, OrigVNI); + MergableSpillsMap::iterator VI = MergableSpills.find(MIdx); + if (VI == MergableSpills.end()) + std::tie(VI, Inserted) = + MergableSpills.insert(std::make_pair(MIdx, std::set())); + VI->second.insert(Spill); + int size = VI->second.size(); + assert(size > 0); +} + +void InlineSpiller::rmFromMergableSpills(MachineInstr *Spill) { + SlotIndex Idx = LIS.getInstructionIndex(Spill); + VNInfo *OrigVNI = LIS.getInterval(Original).getVNInfoAt(Idx.getRegSlot()); + std::pair MIdx = std::make_pair(StackSlot, OrigVNI); + std::set &SpillsSet = MergableSpills[MIdx]; + std::set::iterator SI = SpillsSet.begin(); + for (; SI != SpillsSet.end(); SI++) { + if (*SI == Spill) { + SpillsSet.erase(SI); + return; + } + } +} + +bool InlineSpiller::isSpillCandBB(unsigned OrigReg, VNInfo *OrigVNI, + MachineBasicBlock *BB, unsigned &LiveReg) { + SlotIndex Idx; + MachineBasicBlock::iterator MI = BB->getFirstTerminator(); + if (MI != BB->end()) + Idx = LIS.getInstructionIndex(MI); + else + Idx = LIS.getMBBEndIdx(BB).getPrevSlot(); + std::set &Siblings = VRM.getSiblings(OrigReg); + LiveInterval &OrigLI = LIS.getInterval(OrigReg); + VNInfo *BBVNI = OrigLI.getVNInfoAt(Idx); + assert(BBVNI == OrigVNI && "Unexpected VNI"); + + for (auto const ent : Siblings) { + LiveInterval &LI = LIS.getInterval(ent); + VNInfo *VNI = LI.getVNInfoAt(Idx); + if (VNI) { + LiveReg = ent; + return true; + } + } + return false; +} + +void InlineSpiller::runHoistSpills( + unsigned OrigReg, VNInfo *OrigVNI, std::set &Spills, + std::set &SpillsToRm, + std::set> &SpillsToIns) { + // Clear non-live silbings. + std::set &Siblings = VRM.getSiblings(OrigReg); + std::set::iterator SibIt = Siblings.begin(), SibNextIt; + for (SibNextIt = SibIt; SibIt != Siblings.end(); SibIt = SibNextIt) { + SibNextIt++; + if (MRI.def_empty(*SibIt)) + Siblings.erase(SibIt); + } + + // SpillsToKept keeps the dom tree nodes where spills are to be + // inserted after hoist. If the spill to be inserted is an original + // spill (not hoisted), the value of the map entry is 0. If the spill + // is a hoisted spill, the value of the map entry is the VReg to + // be used in the right side of the store. + DenseMap SpillsToKept; + DenseMap SpillBBToSpill; + for (const auto Spill : Spills) { + MachineBasicBlock *Block = Spill->getParent(); + SpillsToKept[MDT.DT->getNode(Block)] = 0; + SpillBBToSpill[MDT.DT->getNode(Block)] = Spill; + } + + // Get the preorder walk order of the dominator tree. + SmallVector Orders; + SmallVector WorkList; + MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI->def); + WorkList.push_back(MDT.DT->getNode(Root)); + do { + MachineDomTreeNode *Node = WorkList.pop_back_val(); + Orders.push_back(Node); + // Don't include children of BB if the BB contains original spill. + if (SpillsToKept.find(Node) != SpillsToKept.end()) + continue; + const std::vector &Children = Node->getChildren(); + unsigned NumChildren = Children.size(); + for (unsigned i = 0; i != NumChildren; ++i) { + MachineDomTreeNode *Child = Children[i]; + WorkList.push_back(Child); + } + } while (!WorkList.empty()); + + // Perform a reverse preorder walk of the dominator tree. Once we visit + // a dom tree node, we know its children has already been visited. + // SpillsInSubTree keeps the map from a dom tree node to a nodes set. + // It indicates the places where spills are to be inserted in the subtree + // of the dom node for now. + DenseMap> + SpillsInSubTree; + SmallVector::reverse_iterator RIt = Orders.rbegin(); + for (; RIt != Orders.rend(); RIt++) { + MachineBasicBlock *Block = (*RIt)->getBlock(); + + // If Block contains an original spill, simply continue. + if (SpillsToKept.find(*RIt) != SpillsToKept.end() && !SpillsToKept[*RIt]) { + SpillsInSubTree[*RIt].insert(*RIt); + continue; + } + + // Collect spills in subtree of current node (*RIt) to SubSpills. + std::set SubSpills; + const std::vector &Children = (*RIt)->getChildren(); + unsigned NumChildren = Children.size(); + for (unsigned i = 0; i != NumChildren; ++i) { + MachineDomTreeNode *Child = Children[i]; + std::set_union(SubSpills.begin(), SubSpills.end(), + SpillsInSubTree[Child].begin(), + SpillsInSubTree[Child].end(), + std::inserter(SubSpills, SubSpills.begin())); + // Whenever Child's parent is visited, and after the information of + // SpillsInSubTree[Child] has been transfered to SubSpills, we + // erase SpillsInSubTree[Child]. Because after the parent is visited, + // SpillsInSubTree[Child] will become outdated. We don't want the + // outdated information stay there and be accessed mistakenly. + SpillsInSubTree.erase(Child); + } + + // No spills in subtree, simply continue. + if (SubSpills.empty()) + continue; + + // Check whether Block is a possible candidate to insert spill. + unsigned LiveReg = 0; + if (!isSpillCandBB(OrigReg, OrigVNI, Block, LiveReg)) { + for (const auto SpillBB : SubSpills) + SpillsInSubTree[*RIt].insert(SpillBB); + continue; + } + + // Get existing cost of all the spills in SubSpills. + BlockFrequency SpillCost = 0; + for (const auto SpillBB : SubSpills) + SpillCost += MBFI.getBlockFreq(SpillBB->getBlock()); + + // Decide whether to hoist the spills to current node. + // If there are multiple spills that could be merged, bias a little + // to hoist the spill. + BranchProbability MarginProb = (SubSpills.size() > 1) + ? BranchProbability(9, 10) + : BranchProbability(1, 1); + if (SpillCost > MBFI.getBlockFreq(Block) * MarginProb) { + // Hoist: Move spills to Block. + for (const auto SpillBB : SubSpills) { + // When SpillBB is a BB contains original spill, insert the spill + // to SpillsToRm. + if (SpillsToKept.find(SpillBB) != SpillsToKept.end() && + !SpillsToKept[SpillBB]) { + MachineInstr *SpillToRm = SpillBBToSpill[SpillBB]; + SpillsToRm.insert(SpillToRm); + } + SpillsToKept.erase(SpillBB); + } + SpillsToKept[*RIt] = LiveReg; + SpillsInSubTree[*RIt].insert(*RIt); + DEBUG({ + dbgs() << "spills in BB: "; + for (auto &Rspill : SubSpills) + dbgs() << Rspill->getBlock()->getNumber() << " "; + dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber() + << "\n"; + }); + } else { + // Don't Hoist: keep spills in their original places. + for (const auto SpillBB : SubSpills) + SpillsInSubTree[*RIt].insert(SpillBB); + } + } + // For spills in SpillsToKept with LiveReg set, save them to SpillsToIns. + for (const auto ent : SpillsToKept) { + if (ent.second) + SpillsToIns.insert(std::make_pair(ent.first->getBlock(), ent.second)); + } +} + +void InlineSpiller::hoistAllSpills() { + // Save the mapping between stackslot and its original reg. + DenseMap SlotToOrigReg; + for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + int Slot = VRM.getStackSlot(Reg); + if (Slot != VirtRegMap::NO_STACK_SLOT) { + for (auto &ent : MergableSpills) { + if (ent.first.first == Slot && + SlotToOrigReg.find(Slot) == SlotToOrigReg.end()) + SlotToOrigReg[Slot] = VRM.getOriginal(Reg); + } + } + } + + for (auto &ent : MergableSpills) { + int Slot = ent.first.first; + unsigned OrigReg = SlotToOrigReg[Slot]; + VNInfo *OrigVNI = ent.first.second; + std::set &EqValSpills = ent.second; + + DEBUG({ + dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n" + << "Equal spills in BB: "; + for (auto &spill : EqValSpills) + dbgs() << spill->getParent()->getNumber() << " "; + dbgs() << "\n"; + }); + + // First, clean up all the redundent spills. + std::set SpillsToRm; + std::set> SpillsToIns; + std::set::iterator SI = EqValSpills.begin(); + std::set::iterator SJ; + for (; SI != EqValSpills.end(); SI++) { + for (SJ = SI, SJ++; SJ != EqValSpills.end(); SJ++) { + MachineBasicBlock *SIBB = (*SI)->getParent(); + MachineBasicBlock *SJBB = (*SJ)->getParent(); + if (MDT.properlyDominates(SIBB, SJBB)) + SpillsToRm.insert(*SJ); + else if (MDT.properlyDominates(SJBB, SIBB)) + SpillsToRm.insert(*SI); + else if (SIBB == SJBB) { + SlotIndex IdxI = LIS.getInstructionIndex(*SI); + SlotIndex IdxJ = LIS.getInstructionIndex(*SJ); + SpillsToRm.insert((IdxI > IdxJ) ? *SI : *SJ); + } + } + } + for (auto &Rspill : SpillsToRm) + EqValSpills.erase(Rspill); + + DEBUG({ + dbgs() << "Trivially redundent spills in BB: "; + for (auto &Rspill : SpillsToRm) + dbgs() << Rspill->getParent()->getNumber() << " "; + dbgs() << "\n"; + }); + + // Try to hoist spills according to BB hotness. The result is saved + // in SpillsToRm and SpillsToIns + runHoistSpills(OrigReg, OrigVNI, EqValSpills, SpillsToRm, SpillsToIns); + + DEBUG({ + dbgs() << "Finally inserted spills in BB: "; + for (auto &Ispill : SpillsToIns) + dbgs() << Ispill.first->getNumber() << " "; + dbgs() << "\nFinally removed spills in BB: "; + for (auto &Rspill : SpillsToRm) + dbgs() << Rspill->getParent()->getNumber() << " "; + dbgs() << "\n"; + }); + + LiveInterval &StackIntvl = LSS.getInterval(Slot); + if (!SpillsToIns.empty() || !SpillsToRm.empty()) { + LiveInterval &OrigLI = LIS.getInterval(OrigReg); + StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI, + StackIntvl.getValNumInfo(0)); + } + + // Insert hoisted spills. + for (auto const &ent : SpillsToIns) { + MachineBasicBlock *BB = ent.first; + unsigned LiveReg = ent.second; + MachineBasicBlock::iterator MI = BB->getFirstTerminator(); + TII.storeRegToStackSlot(*BB, MI, LiveReg, false, Slot, + MRI.getRegClass(LiveReg), &TRI); + LIS.InsertMachineInstrRangeInMaps(std::prev(MI), MI); + ++NumSpills; + } + + // Remove redundent spills. + for (auto const &ent : SpillsToRm) { + LIS.RemoveMachineInstrFromMaps(ent); + ent->eraseFromParent(); + --NumSpills; + } + } +} Index: lib/CodeGen/LiveRangeEdit.cpp =================================================================== --- lib/CodeGen/LiveRangeEdit.cpp +++ lib/CodeGen/LiveRangeEdit.cpp @@ -35,6 +35,7 @@ unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg)); if (VRM) { VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg)); + VRM->setIsSiblingsOfReg(VRM->getOriginal(OldReg), VReg); } LiveInterval &LI = LIS.createEmptyInterval(VReg); return LI; @@ -44,6 +45,7 @@ unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg)); if (VRM) { VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg)); + VRM->setIsSiblingsOfReg(VRM->getOriginal(OldReg), VReg); } return VReg; } Index: lib/CodeGen/RegAllocGreedy.cpp =================================================================== --- lib/CodeGen/RegAllocGreedy.cpp +++ lib/CodeGen/RegAllocGreedy.cpp @@ -44,6 +44,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/Timer.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" #include @@ -2601,6 +2602,8 @@ allocatePhysRegs(); tryHintsRecoloring(); + spiller().hoistAllSpills(); + releaseMemory(); return true; } Index: lib/CodeGen/Spiller.h =================================================================== --- lib/CodeGen/Spiller.h +++ lib/CodeGen/Spiller.h @@ -29,6 +29,9 @@ /// spill - Spill the LRE.getParent() live interval. virtual void spill(LiveRangeEdit &LRE) = 0; + /// hoistAllSpills - Hoist Spills to place them in less frequent executed BB + /// and remove redundent spills. + virtual void hoistAllSpills() = 0; }; /// Create and return a spiller that will insert spill code directly instead Index: lib/CodeGen/VirtRegMap.cpp =================================================================== --- lib/CodeGen/VirtRegMap.cpp +++ lib/CodeGen/VirtRegMap.cpp @@ -62,6 +62,7 @@ Virt2PhysMap.clear(); Virt2StackSlotMap.clear(); Virt2SplitMap.clear(); + Virt2SiblingsMap.clear(); grow(); return false; @@ -72,6 +73,7 @@ Virt2PhysMap.resize(NumRegs); Virt2StackSlotMap.resize(NumRegs); Virt2SplitMap.resize(NumRegs); + Virt2SiblingsMap.resize(NumRegs); } unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {