X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.cpp;h=942d8d95cf993bf740c57efa96adf4bfa20a420c;hb=ef4cfc749a61d0d0252196c957697436ba7ec068;hp=f0b0d58d13587969c01baf934457f10795bcdce8;hpb=8c08d8c77c45d4721e7d3ef746cca9e39b28e379;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index f0b0d58d135..942d8d95cf9 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -42,6 +42,7 @@ STATISTIC(numExtends , "Number of copies extended"); STATISTIC(NumReMats , "Number of instructions re-materialized"); STATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); STATISTIC(numAborts , "Number of times interval joining aborted"); +STATISTIC(numDeadValNo, "Number of valno def marked dead"); char SimpleRegisterCoalescing::ID = 0; static cl::opt @@ -450,6 +451,98 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, return true; } +/// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply +/// fallthoughs to SuccMBB. +static bool isSameOrFallThroughBB(MachineBasicBlock *MBB, + MachineBasicBlock *SuccMBB, + const TargetInstrInfo *tii_) { + if (MBB == SuccMBB) + return true; + MachineBasicBlock *TBB = 0, *FBB = 0; + SmallVector Cond; + return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB && + MBB->isSuccessor(SuccMBB); +} + +/// removeRange - Wrapper for LiveInterval::removeRange. This removes a range +/// from a physical register live interval as well as from the live intervals +/// of its sub-registers. +static void removeRange(LiveInterval &li, unsigned Start, unsigned End, + LiveIntervals *li_, const TargetRegisterInfo *tri_) { + li.removeRange(Start, End, true); + if (TargetRegisterInfo::isPhysicalRegister(li.reg)) { + for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { + if (!li_->hasInterval(*SR)) + continue; + LiveInterval &sli = li_->getInterval(*SR); + unsigned RemoveEnd = Start; + while (RemoveEnd != End) { + LiveInterval::iterator LR = sli.FindLiveRangeContaining(Start); + if (LR == sli.end()) + break; + RemoveEnd = (LR->end < End) ? LR->end : End; + sli.removeRange(Start, RemoveEnd, true); + Start = RemoveEnd; + } + } + } +} + +/// TrimLiveIntervalToLastUse - If there is a last use in the same basic block +/// as the copy instruction, trim the live interval to the last use and return +/// true. +bool +SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(unsigned CopyIdx, + MachineBasicBlock *CopyMBB, + LiveInterval &li, + const LiveRange *LR) { + unsigned MBBStart = li_->getMBBStartIdx(CopyMBB); + unsigned LastUseIdx; + MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg, + LastUseIdx); + if (LastUse) { + MachineInstr *LastUseMI = LastUse->getParent(); + if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) { + // r1024 = op + // ... + // BB1: + // = r1024 + // + // BB2: + // r1025 = r1024 + if (MBBStart < LR->end) + removeRange(li, MBBStart, LR->end, li_, tri_); + return true; + } + + // There are uses before the copy, just shorten the live range to the end + // of last use. + LastUse->setIsKill(); + removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_); + li.addKill(LR->valno, LastUseIdx+1); + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && + DstReg == li.reg) { + // Last use is itself an identity code. + int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_); + LastUseMI->getOperand(DeadIdx).setIsDead(); + } + return true; + } + + // Is it livein? + if (LR->start <= MBBStart && LR->end > MBBStart) { + if (LR->start == 0) { + assert(TargetRegisterInfo::isPhysicalRegister(li.reg)); + // Live-in to the function but dead. Remove it from entry live-in set. + mf_->begin()->removeLiveIn(li.reg); + } + // FIXME: Shorten intervals in BBs that reaches this BB. + } + + return false; +} + /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial /// computation, replace the copy by rematerialize the definition. bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt, @@ -467,6 +560,9 @@ bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt, const TargetInstrDesc &TID = DefMI->getDesc(); if (!TID.isAsCheapAsAMove()) return false; + if (!DefMI->getDesc().isRematerializable() || + !tii_->isTriviallyReMaterializable(DefMI)) + return false; bool SawStore = false; if (!DefMI->isSafeToMove(tii_, SawStore)) return false; @@ -485,7 +581,12 @@ bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt, } } + // If copy kills the source register, find the last use and propagate + // kill. MachineBasicBlock *MBB = CopyMI->getParent(); + if (CopyMI->killsRegister(SrcInt.reg)) + TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR); + MachineBasicBlock::iterator MII = next(MachineBasicBlock::iterator(CopyMI)); CopyMI->removeFromParent(); tii_->reMaterialize(*MBB, MII, DstReg, DefMI); @@ -660,30 +761,6 @@ void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg, } } -/// removeRange - Wrapper for LiveInterval::removeRange. This removes a range -/// from a physical register live interval as well as from the live intervals -/// of its sub-registers. -static void removeRange(LiveInterval &li, unsigned Start, unsigned End, - LiveIntervals *li_, const TargetRegisterInfo *tri_) { - li.removeRange(Start, End, true); - if (TargetRegisterInfo::isPhysicalRegister(li.reg)) { - for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { - if (!li_->hasInterval(*SR)) - continue; - LiveInterval &sli = li_->getInterval(*SR); - unsigned RemoveEnd = Start; - while (RemoveEnd != End) { - LiveInterval::iterator LR = sli.FindLiveRangeContaining(Start); - if (LR == sli.end()) - break; - RemoveEnd = (LR->end < End) ? LR->end : End; - sli.removeRange(Start, RemoveEnd, true); - Start = RemoveEnd; - } - } - } -} - /// removeIntervalIfEmpty - Check if the live interval of a physical register /// is empty, if so remove it and also remove the empty intervals of its /// sub-registers. Return true if live interval is removed. @@ -752,19 +829,6 @@ static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI, } } -/// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply -/// fallthoughs to SuccMBB. -static bool isSameOrFallThroughBB(MachineBasicBlock *MBB, - MachineBasicBlock *SuccMBB, - const TargetInstrInfo *tii_) { - if (MBB == SuccMBB) - return true; - MachineBasicBlock *TBB = 0, *FBB = 0; - SmallVector Cond; - return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB && - MBB->isSuccessor(SuccMBB); -} - /// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially /// extended by a dead copy. Mark the last use (if any) of the val# as kill as /// ends the live range there. If there isn't another use, then this live range @@ -796,55 +860,31 @@ SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li, // More uses past this copy? Nothing to do. return false; + // If there is a last use in the same bb, we can't remove the live range. + // Shorten the live interval and return. MachineBasicBlock *CopyMBB = CopyMI->getParent(); - unsigned MBBStart = li_->getMBBStartIdx(CopyMBB); - unsigned LastUseIdx; - MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg, - LastUseIdx); - if (LastUse) { - MachineInstr *LastUseMI = LastUse->getParent(); - if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) { - // r1024 = op - // ... - // BB1: - // = r1024 - // - // BB2: - // r1025 = r1024 - if (MBBStart < LR->end) - removeRange(li, MBBStart, LR->end, li_, tri_); - return false; - } - - // There are uses before the copy, just shorten the live range to the end - // of last use. - LastUse->setIsKill(); - removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_); - unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; - if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && - DstReg == li.reg) { - // Last use is itself an identity code. - int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_); - LastUseMI->getOperand(DeadIdx).setIsDead(); - } + if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR)) return false; - } - // Is it livein? - if (LR->start <= MBBStart && LR->end > MBBStart) { - if (LR->start == 0) { - assert(TargetRegisterInfo::isPhysicalRegister(li.reg)); - // Live-in to the function but dead. Remove it from entry live-in set. - mf_->begin()->removeLiveIn(li.reg); + MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart); + if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_)) + // If the live range starts in another mbb and the copy mbb is not a fall + // through mbb, then we can only cut the range from the beginning of the + // copy mbb. + RemoveStart = li_->getMBBStartIdx(CopyMBB) + 1; + + if (LR->valno->def == RemoveStart) { + // If the def MI defines the val# and this copy is the only kill of the + // val#, then propagate the dead marker. + if (li.isOnlyLROfValNo(LR)) { + PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_); + ++numDeadValNo; } - // FIXME: Shorten intervals in BBs that reaches this BB. + if (li.isKill(LR->valno, RemoveEnd)) + li.removeKill(LR->valno, RemoveEnd); } - if (LR->valno->def == RemoveStart) - // If the def MI defines the val#, propagate the dead marker. - PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_); - - removeRange(li, RemoveStart, LR->end, li_, tri_); + removeRange(li, RemoveStart, RemoveEnd, li_, tri_); return removeIntervalIfEmpty(li, li_, tri_); } @@ -928,9 +968,10 @@ void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li, LastUse = MO; } } - if (LastUse) + if (LastUse) { LastUse->setIsKill(); - else { + li.addKill(VNI, LastUseIdx+1); + } else { // Remove dead implicit_def's. while (!ImpDefs.empty()) { MachineInstr *ImpDef = ImpDefs.back(); @@ -1290,8 +1331,13 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { } } + // If we are joining two virtual registers and the resulting register + // class is more restrictive (fewer register, smaller size). Check if it's + // worth doing the merge. if (!SrcIsPhys && !DstIsPhys && - !isWinToJoinCrossClass(LargeReg, SmallReg, Limit)) { + (isExtSubReg || DstRC->isASubClass()) && + !isWinToJoinCrossClass(LargeReg, SmallReg, + allocatableRCRegs_[NewRC].count())) { DOUT << "\tSrc/Dest are different register classes.\n"; // Allow the coalescer to try again in case either side gets coalesced to // a physical register that's compatible with the other side. e.g. @@ -1317,6 +1363,15 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { DOUT << " and "; DstInt.print(DOUT, tri_); DOUT << ": "; + // Save a copy of the virtual register live interval. We'll manually + // merge this into the "real" physical register live interval this is + // coalesced with. + LiveInterval *SavedLI = 0; + if (RealDstReg) + SavedLI = li_->dupInterval(&SrcInt); + else if (RealSrcReg) + SavedLI = li_->dupInterval(&DstInt); + // Check if it is necessary to propagate "isDead" property. if (!isExtSubReg && !isInsSubReg) { MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false); @@ -1408,21 +1463,17 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { if (RealDstReg || RealSrcReg) { LiveInterval &RealInt = li_->getOrCreateInterval(RealDstReg ? RealDstReg : RealSrcReg); - SmallSet CopiedValNos; - for (LiveInterval::Ranges::const_iterator I = ResSrcInt->ranges.begin(), - E = ResSrcInt->ranges.end(); I != E; ++I) { - const LiveRange *DstLR = ResDstInt->getLiveRangeContaining(I->start); - assert(DstLR && "Invalid joined interval!"); - const VNInfo *DstValNo = DstLR->valno; - if (CopiedValNos.insert(DstValNo)) { - VNInfo *ValNo = RealInt.getNextValue(DstValNo->def, DstValNo->copy, - li_->getVNInfoAllocator()); - ValNo->hasPHIKill = DstValNo->hasPHIKill; - RealInt.addKills(ValNo, DstValNo->kills); - RealInt.MergeValueInAsValue(*ResDstInt, DstValNo, ValNo); - } + for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(), + E = SavedLI->vni_end(); I != E; ++I) { + const VNInfo *ValNo = *I; + VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->copy, + li_->getVNInfoAllocator()); + NewValNo->hasPHIKill = ValNo->hasPHIKill; + NewValNo->redefByEC = ValNo->redefByEC; + RealInt.addKills(NewValNo, ValNo->kills); + RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo); } - + RealInt.weight += SavedLI->weight; DstReg = RealDstReg ? RealDstReg : RealSrcReg; } @@ -1492,6 +1543,12 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { // being merged. li_->removeInterval(SrcReg); + // Manually deleted the live interval copy. + if (SavedLI) { + SavedLI->clear(); + delete SavedLI; + } + if (isEmpty) { // Now the copy is being coalesced away, the val# previously defined // by the copy is being defined by an IMPLICIT_DEF which defines a zero @@ -2276,7 +2333,7 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, unsigned Idx = li_->getInstructionIndex(UseMI); if (Idx >= Start && Idx < End && Idx >= UseIdx) { LastUse = &Use; - UseIdx = Idx; + UseIdx = li_->getUseIndex(Idx); } } return LastUse; @@ -2302,7 +2359,7 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, MachineOperand &Use = MI->getOperand(i); if (Use.isReg() && Use.isUse() && Use.getReg() && tri_->regsOverlap(Use.getReg(), Reg)) { - UseIdx = e; + UseIdx = li_->getUseIndex(e); return &Use; } } @@ -2444,6 +2501,8 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); + if (!Reg) + continue; if (TargetRegisterInfo::isVirtualRegister(Reg)) DeadDefs.push_back(Reg); if (MO.isDead())