Index: llvm/trunk/lib/CodeGen/LiveIntervalAnalysis.cpp =================================================================== --- llvm/trunk/lib/CodeGen/LiveIntervalAnalysis.cpp +++ llvm/trunk/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -1044,6 +1044,24 @@ for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO) if (MO->isReg() && MO->isUse()) MO->setIsKill(false); + + // Is there a def before NewIdx which is not OldIdx? + LiveRange::iterator Next = std::next(OldIdxIn); + if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) && + SlotIndex::isEarlierInstr(Next->start, NewIdx)) { + // If we are here then OldIdx was just a use but not a def. We only have + // to ensure liveness extends to NewIdx. + LiveRange::iterator NewIdxIn = + LR.advanceTo(Next, NewIdx.getBaseIndex()); + // Extend the segment before NewIdx if necessary. + if (NewIdxIn == E || + !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) { + LiveRange::iterator Prev = std::prev(NewIdxIn); + Prev->end = NewIdx.getRegSlot(); + } + return; + } + // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR // invalid by overlapping ranges. bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); @@ -1053,7 +1071,7 @@ return; // Did we have a Def at OldIdx? - OldIdxOut = std::next(OldIdxIn); + OldIdxOut = Next; if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) return; } else { @@ -1077,14 +1095,80 @@ } // If we are here then we have a Definition at OldIdx which ends before - // NewIdx. Moving across unrelated defs is not allowed; That means we either - // had a dead-def at OldIdx or the OldIdxOut segment ends at NewIdx. - assert((OldIdxOut->end == OldIdx.getDeadSlot() || - SlotIndex::isSameInstr(OldIdxOut->end, NewIdxDef)) && - "Cannot move def below kill"); + // NewIdx. + // Is there an existing Def at NewIdx? LiveRange::iterator AfterNewIdx = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot()); + bool OldIdxDefIsDead = OldIdxOut->end.isDead(); + if (!OldIdxDefIsDead && + SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) { + // OldIdx is not a dead def, and NewIdxDef is inside a new interval. + VNInfo *DefVNI; + if (OldIdxOut != LR.begin() && + !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end, + OldIdxOut->start)) { + // There is no gap between OldIdxOut and its predecessor anymore, + // merge them + LiveRange::iterator IPrev = std::prev(OldIdxOut); + DefVNI = OldIdxVNI; + IPrev->end = OldIdxOut->end; + } else { + // The value is live in to OldIdx + LiveRange::iterator INext = std::next(OldIdxOut); + assert(INext != E && "Must have following segment"); + // We merge OldIdxOut and its successor. As we're dealing with subreg + // reordering, there is always a successor to OldIdxOut in the same BB + // We don't need INext->valno anymore and will reuse for the new segment + // we create later. + DefVNI = INext->valno; + INext->start = OldIdxOut->end; + INext->valno = OldIdxVNI; + INext->valno->def = INext->start; + } + // If NewIdx is behind the last segment, extend that and append a new one. + if (AfterNewIdx == E) { + // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up + // one position. + // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end + // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end + std::copy(std::next(OldIdxOut), E, OldIdxOut); + // The last segment is undefined now, reuse it for a dead def. + LiveRange::iterator NewSegment = std::prev(E); + *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), + DefVNI); + DefVNI->def = NewIdxDef; + + LiveRange::iterator Prev = std::prev(NewSegment); + Prev->end = NewIdxDef; + } else { + // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up + // one position. + // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -| + // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -| + std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut); + LiveRange::iterator Prev = std::prev(AfterNewIdx); + // We have two cases: + if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) { + // Case 1: NewIdx is inside a liverange. Split this liverange at + // NewIdxDef into the segment "Prev" followed by "NewSegment". + LiveRange::iterator NewSegment = AfterNewIdx; + *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno); + Prev->valno->def = NewIdxDef; + + *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI); + DefVNI->def = Prev->start; + } else { + // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and + // turn Prev into a segment from NewIdx to AfterNewIdx->start. + *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI); + DefVNI->def = NewIdxDef; + assert(DefVNI != AfterNewIdx->valno); + } + } + return; + } + if (AfterNewIdx != E && SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) { // There is an existing def at NewIdx. The def at OldIdx is coalesced into @@ -1130,24 +1214,18 @@ return; // At this point we have to move OldIdxIn->end back to the nearest - // previous use but no further than NewIdx. Moreover OldIdx is a Def then - // we cannot have any intermediate uses or the move would be illegal. + // previous use or (dead-)def but no further than NewIdx. + SlotIndex DefBeforeOldIdx = std::max(OldIdxIn->start.getDeadSlot(), + NewIdx.getRegSlot()); + OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask); + // Did we have a Def at OldIdx? If not we are done now. OldIdxOut = std::next(OldIdxIn); - // Did we have a Def at OldIdx? - if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) { - // No def, search for the nearest previous use. - // This can never be an early clobber kill since there is no def. - OldIdxIn->end = findLastUseBefore(Reg, LaneMask).getRegSlot(); - // We are done if there is no def at OldIdx. + if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)) return; - } else { - // There can't have been any intermediate uses or defs, so move - // OldIdxIn->end to NewIdx. - OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()); - } } else { OldIdxOut = OldIdxIn; + OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E; } // If we are here then there is a Definition at OldIdx. OldIdxOut points @@ -1179,9 +1257,49 @@ // Previously nothing was live after NewIdx, so all we have to do now is // move the begin of OldIdxOut to NewIdx. if (!OldIdxDefIsDead) { - // Leave the end point of a live def. - OldIdxVNI->def = NewIdxDef; - OldIdxOut->start = NewIdxDef; + // Do we have any intermediate Defs between OldIdx and NewIdx? + if (OldIdxIn != E && + SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) { + // OldIdx is not a dead def and NewIdx is before predecessor start + LiveRange::iterator NewIdxIn = NewIdxOut; + assert(NewIdxIn == LR.find(NewIdx.getBaseIndex())); + const SlotIndex SplitPos = NewIdxDef; + + // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut. + *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end, + OldIdxIn->valno); + // OldIdxIn and OldIdxVNI are now undef and can be overridden. + // We Slide [NewIdxIn, OldIdxIn) down one position. + // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -| + // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -| + std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut); + // NewIdxIn is now considered undef so we can reuse it for the moved + // value. + LiveRange::iterator NewSegment = NewIdxIn; + LiveRange::iterator Next = std::next(NewSegment); + NewSegment->valno = OldIdxVNI; + if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) { + // There is no gap between NewSegment and its predecessor + *NewSegment = LiveRange::Segment(Next->start, SplitPos, + NewSegment->valno); + NewSegment->valno->def = Next->start; + + *Next = LiveRange::Segment(SplitPos, Next->end, Next->valno); + Next->valno->def = SplitPos; + } else { + // There is a gap between NewSegment and its predecessor + // Value become live in + *NewSegment = LiveRange::Segment(SplitPos, Next->start, + NewSegment->valno); + NewSegment->valno->def = SplitPos; + } + } else { + // Leave the end point of a live def. + OldIdxOut->start = NewIdxDef; + OldIdxVNI->def = NewIdxDef; + if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end)) + OldIdxIn->end = NewIdx.getRegSlot(); + } } else { // OldIdxVNI is a dead def. It may have been moved across other values // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut) @@ -1215,10 +1333,10 @@ } // Return the last use of reg between NewIdx and OldIdx. - SlotIndex findLastUseBefore(unsigned Reg, LaneBitmask LaneMask) { - + SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg, + LaneBitmask LaneMask) { if (TargetRegisterInfo::isVirtualRegister(Reg)) { - SlotIndex LastUse = NewIdx; + SlotIndex LastUse = Before; for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) { unsigned SubReg = MO.getSubReg(); if (SubReg != 0 && LaneMask != 0 @@ -1228,16 +1346,16 @@ const MachineInstr *MI = MO.getParent(); SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); if (InstSlot > LastUse && InstSlot < OldIdx) - LastUse = InstSlot; + LastUse = InstSlot.getRegSlot(); } return LastUse; } // This is a regunit interval, so scanning the use list could be very // expensive. Scan upwards from OldIdx instead. - assert(NewIdx < OldIdx && "Expected upwards move"); + assert(Before < OldIdx && "Expected upwards move"); SlotIndexes *Indexes = LIS.getSlotIndexes(); - MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx); + MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before); // OldIdx may not correspond to an instruction any longer, so set MII to // point to the next instruction after OldIdx, or MBB->end(). @@ -1253,19 +1371,19 @@ continue; SlotIndex Idx = Indexes->getInstructionIndex(MII); - // Stop searching when NewIdx is reached. - if (!SlotIndex::isEarlierInstr(NewIdx, Idx)) - return NewIdx; + // Stop searching when Before is reached. + if (!SlotIndex::isEarlierInstr(Before, Idx)) + return Before; // Check if MII uses Reg. for (MIBundleOperands MO(MII); MO.isValid(); ++MO) if (MO->isReg() && TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && TRI.hasRegUnit(MO->getReg(), Reg)) - return Idx; + return Idx.getRegSlot(); } - // Didn't reach NewIdx. It must be the first instruction in the block. - return NewIdx; + // Didn't reach Before. It must be the first instruction in the block. + return Before; } };