From a2e6435e483f30e00382a5758f6dcc67e213b57a Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Wed, 11 Mar 2009 00:03:21 +0000 Subject: [PATCH] Two coalescer fixes in one. 1. Use the same value# to represent unknown values being merged into sub-registers. 2. When coalescer commute an instruction and the destination is a physical register, update its sub-registers by merging in the extended ranges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@66610 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveInterval.h | 9 +++++ lib/CodeGen/LiveInterval.cpp | 43 ++++++++++++++++++++- lib/CodeGen/SimpleRegisterCoalescing.cpp | 26 ++++++++++--- test/CodeGen/X86/2009-03-10-CoalescerBug.ll | 28 ++++++++++++++ 4 files changed, 98 insertions(+), 8 deletions(-) create mode 100644 test/CodeGen/X86/2009-03-10-CoalescerBug.ll diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 1e8202e5f4b..8e99ee7e29f 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -212,6 +212,10 @@ namespace llvm { return VNI; } + /// getUnknownValNo - Find a value# for unknown values, if there isn't one + /// create a new one. + VNInfo *getUnknownValNo(BumpPtrAllocator &VNInfoAllocator); + /// addKill - Add a kill instruction index to the specified value /// number. static void addKill(VNInfo *VNI, unsigned KillIdx) { @@ -296,6 +300,11 @@ namespace llvm { void MergeInClobberRanges(const LiveInterval &Clobbers, BumpPtrAllocator &VNInfoAllocator); + /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a + /// single LiveRange only. + void MergeInClobberRange(unsigned Start, unsigned End, + BumpPtrAllocator &VNInfoAllocator); + /// MergeValueInAsValue - Merge all of the live ranges of a specific val# /// in RHS into this live interval as the specified value number. /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 40f8cd4388d..75cd36dec2c 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -551,6 +551,20 @@ void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS, } } +VNInfo *LiveInterval::getUnknownValNo(BumpPtrAllocator &VNInfoAllocator) { + unsigned i = getNumValNums(); + if (i) { + do { + --i; + VNInfo *VNI = getValNumInfo(i); + if (VNI->def == ~0U && !VNI->copy && + !VNI->hasPHIKill && !VNI->redefByEC && VNI->kills.empty()) + return VNI; + } while (i != 0); + } + return getNextValue(~0U, 0, VNInfoAllocator); +} + /// MergeInClobberRanges - For any live ranges that are not defined in the /// current interval, but are defined in the Clobbers interval, mark them @@ -561,8 +575,7 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers, // Find a value # to use for the clobber ranges. If there is already a value# // for unknown values, use it. - // FIXME: Use a single sentinal number for these! - VNInfo *ClobberValNo = getNextValue(~0U, 0, VNInfoAllocator); + VNInfo *ClobberValNo = getUnknownValNo(VNInfoAllocator); iterator IP = begin(); for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { @@ -587,6 +600,32 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers, } } +void LiveInterval::MergeInClobberRange(unsigned Start, unsigned End, + BumpPtrAllocator &VNInfoAllocator) { + // Find a value # to use for the clobber ranges. If there is already a value# + // for unknown values, use it. + VNInfo *ClobberValNo = getUnknownValNo(VNInfoAllocator); + + iterator IP = begin(); + IP = std::upper_bound(IP, end(), Start); + + // If the start of this range overlaps with an existing liverange, trim it. + if (IP != begin() && IP[-1].end > Start) { + Start = IP[-1].end; + // Trimmed away the whole range? + if (Start >= End) return; + } + // If the end of this range overlaps with an existing liverange, trim it. + if (IP != end() && End > IP->start) { + End = IP->start; + // If this trimmed away the whole range, ignore it. + if (Start == End) return; + } + + // Insert the clobber interval. + addRangeFrom(LiveRange(Start, End, ClobberValNo), IP); +} + /// MergeValueNumberInto - This method is called when two value nubmers /// are found to be equivalent. This eliminates V1, replacing all /// LiveRanges with the V1 value number with the V2 value number. This can diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index 942d8d95cf9..c29ee62c83e 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -193,13 +193,12 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); // If the IntB live range is assigned to a physical register, and if that - // physreg has aliases, + // physreg has sub-registers, update their live intervals as well. if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { - // Update the liveintervals of sub-registers. - for (const unsigned *AS = tri_->getSubRegisters(IntB.reg); *AS; ++AS) { - LiveInterval &AliasLI = li_->getInterval(*AS); - AliasLI.addRange(LiveRange(FillerStart, FillerEnd, - AliasLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator()))); + for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { + LiveInterval &SRLI = li_->getInterval(*SR); + SRLI.addRange(LiveRange(FillerStart, FillerEnd, + SRLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator()))); } } @@ -367,6 +366,9 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, BExtend[ALR->end] = BLR->end; // Update uses of IntA of the specific Val# with IntB. + bool BHasSubRegs = false; + if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) + BHasSubRegs = *tri_->getSubRegisters(IntB.reg); for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg), UE = mri_->use_end(); UI != UE;) { MachineOperand &UseMO = UI.getOperand(); @@ -398,6 +400,9 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx); BHasPHIKill |= DLR->valno->hasPHIKill; assert(DLR->valno->def == DefIdx); + if (BHasSubRegs) + // Don't know how to update sub-register live intervals. + return false; BDeadValNos.push_back(DLR->valno); BExtend[DLR->start] = DLR->end; JoinedCopies.insert(UseMI); @@ -435,6 +440,15 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, if (EI != BExtend.end()) End = EI->second; IntB.addRange(LiveRange(AI->start, End, ValNo)); + + // If the IntB live range is assigned to a physical register, and if that + // physreg has sub-registers, update their live intervals as well. + if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { + for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { + LiveInterval &SRLI = li_->getInterval(*SR); + SRLI.MergeInClobberRange(AI->start, End, li_->getVNInfoAllocator()); + } + } } IntB.addKills(ValNo, BKills); ValNo->hasPHIKill = BHasPHIKill; diff --git a/test/CodeGen/X86/2009-03-10-CoalescerBug.ll b/test/CodeGen/X86/2009-03-10-CoalescerBug.ll new file mode 100644 index 00000000000..3d979e9d739 --- /dev/null +++ b/test/CodeGen/X86/2009-03-10-CoalescerBug.ll @@ -0,0 +1,28 @@ +; RUN: llvm-as < %s | llc -mtriple=x86_64-apple-darwin +; rdar://r6661945 + + %struct.WINDOW = type { i16, i16, i16, i16, i16, i16, i16, i32, i32, i8, i8, i8, i8, i8, i8, i8, i8, i8, i32, %struct.ldat*, i16, i16, i32, i32, %struct.WINDOW*, %struct.pdat, i16, %struct.cchar_t } + %struct.cchar_t = type { i32, [5 x i32] } + %struct.ldat = type { %struct.cchar_t*, i16, i16, i16 } + %struct.pdat = type { i16, i16, i16, i16, i16, i16 } + +define i32 @pnoutrefresh(%struct.WINDOW* %win, i32 %pminrow, i32 %pmincol, i32 %sminrow, i32 %smincol, i32 %smaxrow, i32 %smaxcol) nounwind optsize ssp { +entry: + %0 = load i16* null, align 4 ; [#uses=2] + %1 = icmp sgt i16 0, %0 ; [#uses=1] + br i1 %1, label %bb12, label %bb13 + +bb12: ; preds = %entry + %2 = sext i16 %0 to i32 ; [#uses=1] + %3 = sub i32 %2, 0 ; [#uses=1] + %4 = add i32 %3, %smaxrow ; [#uses=2] + %5 = trunc i32 %4 to i16 ; [#uses=1] + %6 = add i16 0, %5 ; [#uses=1] + br label %bb13 + +bb13: ; preds = %bb12, %entry + %pmaxrow.0 = phi i16 [ %6, %bb12 ], [ 0, %entry ] ; [#uses=0] + %smaxrow_addr.0 = phi i32 [ %4, %bb12 ], [ %smaxrow, %entry ] ; [#uses=1] + %7 = trunc i32 %smaxrow_addr.0 to i16 ; [#uses=0] + ret i32 0 +} -- 2.34.1