Re: [llvm-commits] [llvm] r47046 - in /llvm/trunk: include/llvm/CodeGen/LiveIntervalAnalysis.h lib/CodeGen/SimpleRegisterCoalescing.cpp lib/CodeGen/SimpleRegisterCoalescing.h
On Feb 12, 2008, at 9:56 PM, Chris Lattner wrote: On Feb 12, 2008, at 7:01 PM, Evan Cheng wrote: Author: evancheng Date: Tue Feb 12 21:01:43 2008 New Revision: 47046 URL: http://llvm.org/viewvc/llvm-project?rev=47046view=rev Log: Initial support for copy elimination by commuting its definition MI. Yay, thanks for tackling this Evan! This speeds up FreeBench/neural by 29%, Olden/bh by 12%, oopack_v1p8 by 53%. Very nice, does it also help shootout/fib? bh speedup doesn't seem real. It doesn't help fib. + // Get the location that B is defined at. Two options: either this value has + // an unknown definition point or it is defined at CopyIdx. If unknown, we + // can't process it. + if (!BValNo-reg) return false; + assert(BValNo-def == CopyIdx Copy doesn't define the value?); + + // AValNo is the value number in A that defines the copy, A3 in the example. + LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1); + VNInfo *AValNo = ALR-valno; This idiom happens a lot in the preexisting code. Please use: VNInfo *AValNo = IntA.FindLiveRangeContaining(CopyIdx-1)-valno; ALR is also used below. Or better yet, add a new method that returns valno directly. + int Idx = -1; Idx is too generic of a name for a variable with this long of lifetime, please name it something more descriptive. What type of idx is it? + for (unsigned i = 0, e = DefMI-getNumOperands(); i != e; ++i) { This loop needs a comment. What are you trying to find with this loop? Maybe it should be moved out to its own function which just returns idx? This would force you to name it, which would describe what it does :) There is a reason I said initial in the commit message. This is not done. I need a target hook to tell me what is the new destination register after commuting. Right now this is basically assuming x86 commutable instructions: A = A + B Another random question unrelated to this code: now that we have efficient RAUW, can we eliminate the 'rep' mapping stuff and just RAUW vregs as they are coallesced? Well, actually it's related. I think it's required for correctness. See below. + MachineBasicBlock *MBB = DefMI-getParent(); + MachineInstr *NewMI = tii_-commuteInstruction(DefMI); + if (NewMI != DefMI) { +li_-ReplaceMachineInstrInMaps(DefMI, NewMI); +MBB-insert(DefMI, NewMI); +MBB-erase(DefMI); + } + unsigned OpIdx = NewMI-findRegisterUseOperandIdx(IntA.reg); + NewMI-getOperand(OpIdx).setIsKill(); + + // Update uses of IntA of the specific Val# with IntB. + bool BHasPHIKill = BValNo-hasPHIKill; + SmallVectorVNInfo*, 4 BDeadValNos; + SmallVectorunsigned, 4 BKills; + std::mapunsigned, unsigned BExtend; + for (MachineRegisterInfo::use_iterator UI = mri_- use_begin(IntA.reg), + UE = mri_-use_end(); UI != UE;) { Yay for use_iterators :) Except I don't think this is quite right. Iterating through uses of IntA.reg means we end up not updating other uses that have already been coalesced to it. +MachineOperand UseMO = UI.getOperand(); +++UI; +MachineInstr *UseMI = UseMO.getParent(); It would be more clear to use (before the increment): MachineInstr *UseMI = *UI; Note that if an instruction uses a register multiple times, incrementing the iterator could point into another operand of the same instruction. This is rare, but the code needs to handle it correctly. I'm concerned about cases like: r1 = or r2, r2 (which is the copy operation on some targets). Where the use iterator could point to the first r2, and incrementing it could point to the next r2. This could be avoided by not zapping instructions in this loop: move the copy zapping to a walk over a smallset or something. Nothing is being zapped in the loop. Copies that would be zapped are put into a set JoinedCopies. In fact, all uses have to be updated to the new register. +unsigned UseIdx = li_-getInstructionIndex(UseMI); +LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); +if (ULR-valno != AValNo) + continue; +UseMO.setReg(NewReg); +if (UseMO.isKill()) + BKills.push_back(li_-getUseIndex(UseIdx)+1); +if (UseMI != CopyMI) { if (UseMI == CopyMI) continue; + unsigned SrcReg, DstReg; + if (!tii_-isMoveInstr(*UseMI, SrcReg, DstReg)) +continue; + unsigned repDstReg = rep(DstReg); + if (repDstReg != IntB.reg) { +// Update dst register interval val# since its source register has +// changed. +LiveInterval DLI = li_-getInterval(repDstReg); +LiveInterval::iterator DLR = + DLI.FindLiveRangeContaining(li_-getDefIndex(UseIdx)); +DLR-valno-reg = NewReg; +ChangedCopies.insert(UseMI); + } else { +// This copy will become a noop. If it's defining a new val#, +// remove that val# as well. However this live range is
Re: [llvm-commits] [llvm] r47046 - in /llvm/trunk: include/llvm/CodeGen/LiveIntervalAnalysis.h lib/CodeGen/SimpleRegisterCoalescing.cpp lib/CodeGen/SimpleRegisterCoalescing.h
On Feb 13, 2008, at 1:47 AM, Evan Cheng wrote: Very nice, does it also help shootout/fib? bh speedup doesn't seem real. It doesn't help fib. Ok, once things have settled, please take a look at the comments in the bugzilla to see if there are other cases being missed. This idiom happens a lot in the preexisting code. Please use: VNInfo *AValNo = IntA.FindLiveRangeContaining(CopyIdx-1)-valno; ALR is also used below. Ok! + for (unsigned i = 0, e = DefMI-getNumOperands(); i != e; ++i) { This loop needs a comment. What are you trying to find with this loop? Maybe it should be moved out to its own function which just returns idx? This would force you to name it, which would describe what it does :) There is a reason I said initial in the commit message. This is not done. I need a target hook to tell me what is the new destination register after commuting. Right now this is basically assuming x86 commutable instructions: A = A + B Ok. Another random question unrelated to this code: now that we have efficient RAUW, can we eliminate the 'rep' mapping stuff and just RAUW vregs as they are coallesced? Well, actually it's related. I think it's required for correctness. See below. Ah, I see. Well this seems like an independently useful change that will both speed up and simplify coalescing. Are you interested in tackling it as part of this project? Yay for use_iterators :) Except I don't think this is quite right. Iterating through uses of IntA.reg means we end up not updating other uses that have already been coalesced to it. Yeah, that's bad. Where the use iterator could point to the first r2, and incrementing it could point to the next r2. This could be avoided by not zapping instructions in this loop: move the copy zapping to a walk over a smallset or something. Nothing is being zapped in the loop. Copies that would be zapped are put into a set JoinedCopies. In fact, all uses have to be updated to the new register. Ok. It isn't clear to me what this code is doing. It looks like it is looking for the copy that has now becomes an identity copy. Is there some way to factor this with other code that is coallescing copies away? It seems duplicated from somewhere else. It would be nicer to Not really. A number of things are happening here. We are trying to determine which copies are now identity copies and make sure their valno# will be eliminated. We also need to transfer the live ranges defined by the (now dead) copies to the new val# defined by the commuted definition MI. It's also tracking kill information. Ok, please comment it a bit better. Is there any way to avoid this work or factor this out into functions that can be shared with other code? just add all copies to a small vector and then zap them later or something, to keep the logic simple. That's essentially what's happening. This has gone through a number of iterations already. Apart from some cosmetic changes, it's not going to get much simpler than this. ok. Does this need to be an ivar? Can it just be passed by-ref between the methods that need it? This will be cleaned up later as part of RAUW change. Ok. Thanks Evan! -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] [llvm] r47046 - in /llvm/trunk: include/llvm/CodeGen/LiveIntervalAnalysis.h lib/CodeGen/SimpleRegisterCoalescing.cpp lib/CodeGen/SimpleRegisterCoalescing.h
On Feb 13, 2008, at 9:31 AM, Chris Lattner wrote: On Feb 13, 2008, at 1:47 AM, Evan Cheng wrote: Very nice, does it also help shootout/fib? bh speedup doesn't seem real. It doesn't help fib. Ok, once things have settled, please take a look at the comments in the bugzilla to see if there are other cases being missed. This idiom happens a lot in the preexisting code. Please use: VNInfo *AValNo = IntA.FindLiveRangeContaining(CopyIdx-1)-valno; ALR is also used below. Ok! + for (unsigned i = 0, e = DefMI-getNumOperands(); i != e; ++i) { This loop needs a comment. What are you trying to find with this loop? Maybe it should be moved out to its own function which just returns idx? This would force you to name it, which would describe what it does :) There is a reason I said initial in the commit message. This is not done. I need a target hook to tell me what is the new destination register after commuting. Right now this is basically assuming x86 commutable instructions: A = A + B Ok. Another random question unrelated to this code: now that we have efficient RAUW, can we eliminate the 'rep' mapping stuff and just RAUW vregs as they are coallesced? Well, actually it's related. I think it's required for correctness. See below. Ah, I see. Well this seems like an independently useful change that will both speed up and simplify coalescing. Are you interested in tackling it as part of this project? That's the plan. Without RAUW change, I can't enable this optimization. It's *shouldn't* take long. Evan Yay for use_iterators :) Except I don't think this is quite right. Iterating through uses of IntA.reg means we end up not updating other uses that have already been coalesced to it. Yeah, that's bad. Where the use iterator could point to the first r2, and incrementing it could point to the next r2. This could be avoided by not zapping instructions in this loop: move the copy zapping to a walk over a smallset or something. Nothing is being zapped in the loop. Copies that would be zapped are put into a set JoinedCopies. In fact, all uses have to be updated to the new register. Ok. It isn't clear to me what this code is doing. It looks like it is looking for the copy that has now becomes an identity copy. Is there some way to factor this with other code that is coallescing copies away? It seems duplicated from somewhere else. It would be nicer to Not really. A number of things are happening here. We are trying to determine which copies are now identity copies and make sure their valno# will be eliminated. We also need to transfer the live ranges defined by the (now dead) copies to the new val# defined by the commuted definition MI. It's also tracking kill information. Ok, please comment it a bit better. Is there any way to avoid this work or factor this out into functions that can be shared with other code? just add all copies to a small vector and then zap them later or something, to keep the logic simple. That's essentially what's happening. This has gone through a number of iterations already. Apart from some cosmetic changes, it's not going to get much simpler than this. ok. Does this need to be an ivar? Can it just be passed by-ref between the methods that need it? This will be cleaned up later as part of RAUW change. Ok. Thanks Evan! -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] [llvm] r47046 - in /llvm/trunk: include/llvm/CodeGen/LiveIntervalAnalysis.h lib/CodeGen/SimpleRegisterCoalescing.cpp lib/CodeGen/SimpleRegisterCoalescing.h
On Feb 13, 2008, at 10:58 AM, Evan Cheng wrote: Ah, I see. Well this seems like an independently useful change that will both speed up and simplify coalescing. Are you interested in tackling it as part of this project? That's the plan. Without RAUW change, I can't enable this optimization. Awesome, thanks. It's *shouldn't* take long. *crosses fingers* :) -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] [llvm] r47046 - in /llvm/trunk: include/llvm/CodeGen/LiveIntervalAnalysis.h lib/CodeGen/SimpleRegisterCoalescing.cpp lib/CodeGen/SimpleRegisterCoalescing.h
Author: evancheng Date: Tue Feb 12 21:01:43 2008 New Revision: 47046 URL: http://llvm.org/viewvc/llvm-project?rev=47046view=rev Log: Initial support for copy elimination by commuting its definition MI. PR1877. A3 = op A2 B0kill .. B1 = A3 - this copy .. = op A3 - more uses == B2 = op B0 A2kill .. B1 = B2 - now an identify copy .. = op B2 - more uses This speeds up FreeBench/neural by 29%, Olden/bh by 12%, oopack_v1p8 by 53%. Modified: llvm/trunk/include/llvm/CodeGen/LiveIntervalAnalysis.h llvm/trunk/lib/CodeGen/SimpleRegisterCoalescing.cpp llvm/trunk/lib/CodeGen/SimpleRegisterCoalescing.h Modified: llvm/trunk/include/llvm/CodeGen/LiveIntervalAnalysis.h URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/CodeGen/LiveIntervalAnalysis.h?rev=47046r1=47045r2=47046view=diff == --- llvm/trunk/include/llvm/CodeGen/LiveIntervalAnalysis.h (original) +++ llvm/trunk/include/llvm/CodeGen/LiveIntervalAnalysis.h Tue Feb 12 21:01:43 2008 @@ -213,6 +213,20 @@ } } +/// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in +/// maps used by register allocator. +void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { + Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI); + if (mi2i != mi2iMap_.end()) { +i2miMap_[mi2i-second/InstrSlots::NUM] = NewMI; +Mi2IndexMap::const_iterator it = mi2iMap_.find(MI); +assert(it != mi2iMap_.end() Invalid instruction!); +unsigned Index = it-second; +mi2iMap_.erase(MI); +mi2iMap_[NewMI] = Index; + } +} + BumpPtrAllocator getVNInfoAllocator() { return VNInfoAllocator; } virtual void getAnalysisUsage(AnalysisUsage AU) const; Modified: llvm/trunk/lib/CodeGen/SimpleRegisterCoalescing.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/CodeGen/SimpleRegisterCoalescing.cpp?rev=47046r1=47045r2=47046view=diff == --- llvm/trunk/lib/CodeGen/SimpleRegisterCoalescing.cpp (original) +++ llvm/trunk/lib/CodeGen/SimpleRegisterCoalescing.cpp Tue Feb 12 21:01:43 2008 @@ -36,6 +36,8 @@ using namespace llvm; STATISTIC(numJoins, Number of interval joins performed); +STATISTIC(numCommutes , Number of instruction commuting performed); +STATISTIC(numExtends , Number of copies extended); STATISTIC(numPeep , Number of identity moves eliminated after coalescing); STATISTIC(numAborts , Number of times interval joining aborted); @@ -51,6 +53,10 @@ cl::desc(Use new coalescer heuristic), cl::init(false)); + static cl::optbool + CommuteDef(coalescer-commute-instrs, + cl::init(false),
Re: [llvm-commits] [llvm] r47046 - in /llvm/trunk: include/llvm/CodeGen/LiveIntervalAnalysis.h lib/CodeGen/SimpleRegisterCoalescing.cpp lib/CodeGen/SimpleRegisterCoalescing.h
On Feb 12, 2008, at 7:01 PM, Evan Cheng wrote: Author: evancheng Date: Tue Feb 12 21:01:43 2008 New Revision: 47046 URL: http://llvm.org/viewvc/llvm-project?rev=47046view=rev Log: Initial support for copy elimination by commuting its definition MI. Yay, thanks for tackling this Evan! This speeds up FreeBench/neural by 29%, Olden/bh by 12%, oopack_v1p8 by 53%. Very nice, does it also help shootout/fib? +/// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in +/// maps used by register allocator. +void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { + Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI); + if (mi2i != mi2iMap_.end()) { Please change this to: if (mi2i == mi2iMap_.end()) return; ... Just to avoid indentation. +i2miMap_[mi2i-second/InstrSlots::NUM] = NewMI; +Mi2IndexMap::const_iterator it = mi2iMap_.find(MI); +assert(it != mi2iMap_.end() Invalid instruction!); +unsigned Index = it-second; +mi2iMap_.erase(MI); This would avoid another lookup if you used .erase(it); +bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval IntA, + LiveInterval IntB, + MachineInstr *CopyMI) { ... + // Get the location that B is defined at. Two options: either this value has + // an unknown definition point or it is defined at CopyIdx. If unknown, we + // can't process it. + if (!BValNo-reg) return false; + assert(BValNo-def == CopyIdx Copy doesn't define the value?); + + // AValNo is the value number in A that defines the copy, A3 in the example. + LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1); + VNInfo *AValNo = ALR-valno; This idiom happens a lot in the preexisting code. Please use: VNInfo *AValNo = IntA.FindLiveRangeContaining(CopyIdx-1)-valno; Or better yet, add a new method that returns valno directly. + int Idx = -1; Idx is too generic of a name for a variable with this long of lifetime, please name it something more descriptive. What type of idx is it? + for (unsigned i = 0, e = DefMI-getNumOperands(); i != e; ++i) { This loop needs a comment. What are you trying to find with this loop? Maybe it should be moved out to its own function which just returns idx? This would force you to name it, which would describe what it does :) +MachineOperand MO = DefMI-getOperand(i); +if (!MO.isRegister()) continue; +unsigned Reg = MO.getReg(); +if (Reg TargetRegisterInfo::isVirtualRegister(Reg)) { How about: if (Reg == 0 || !isvreg) continue; + if (rep(Reg) == IntA.reg) { +// If the dest register comes from an interval other than IntA, we +// can't handle this. +if (Reg != IntA.reg) + return false; I must be missing something here, how do you know this is a def operand? Another random question unrelated to this code: now that we have efficient RAUW, can we eliminate the 'rep' mapping stuff and just RAUW vregs as they are coallesced? +continue; + } + if (Idx != -1) +// FIXME: Being overly careful here. We just need to figure out the +// which register operand will become the new def. +return false; + Idx = i; +} + } + if (Idx == -1) +// Something like %reg1024 = add %reg1024, %reg1024 +return false; + + MachineOperand MO = DefMI-getOperand(Idx); + unsigned NewReg = MO.getReg(); + if (rep(NewReg) != IntB.reg || !MO.isKill()) +return false; This logic would make more sense if I knew what Idx indicates and why you're rejecting these cases :). Also, MO has a long lifetime, please name it DefMO or something else more descriptive. + // Make sure there are no other definitions of IntB that would reach the + // uses which the new definition can reach. + for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); + AI != AE; ++AI) { +if (AI-valno != AValNo) continue; +LiveInterval::Ranges::iterator BI = + std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI- start); +if (BI != IntB.ranges.begin()) + --BI; +for (; BI != IntB.ranges.end() AI-end = BI-start; ++BI) { + if (BI-valno == BLR-valno) +continue; + if (BI-start = AI-start BI-end AI-start) +return false; + if (BI-start AI-start BI-start AI-end) +return false; +} Please split this out into a static function or a method on liveinterval. + } + + // Commute def machine instr. How about: at this point we have decided that it is legal to do this transformation. Start by commuting the instruction. + MachineBasicBlock *MBB = DefMI-getParent(); + MachineInstr *NewMI = tii_-commuteInstruction(DefMI); + if (NewMI