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=47046&view=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; >> + SmallVector<VNInfo*, 4> BDeadValNos; >> + SmallVector<unsigned, 4> BKills; >> + std::map<unsigned, 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 >> being >> + // extended to the end of the existing live range defined >> by the copy. >> + unsigned DefIdx = li_->getDefIndex(UseIdx); >> + LiveInterval::iterator DLR = >> IntB.FindLiveRangeContaining(DefIdx); >> + BHasPHIKill |= DLR->valno->hasPHIKill; >> + assert(DLR->valno->def == DefIdx); >> + BDeadValNos.push_back(DLR->valno); >> + BExtend[DLR->start] = DLR->end; >> + JoinedCopies.insert(UseMI); >> + // If this is a kill but it's going to be removed, the last >> use >> + // of the same val# is the new kill. >> + if (UseMO.isKill()) { >> + BKills.pop_back(); >> + } >> + } > > 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. > > 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. > > >> = >> = >> = >> = >> = >> = >> = >> = >> = >> ===================================================================== >> --- llvm/trunk/lib/CodeGen/SimpleRegisterCoalescing.h (original) >> +++ llvm/trunk/lib/CodeGen/SimpleRegisterCoalescing.h Tue Feb 12 >> 21:01:43 2008 >> @@ -80,6 +80,7 @@ >> >> + /// ChangedCopies - Keep track of copies modified due to >> commuting. >> + SmallPtrSet<MachineInstr*, 32> ChangedCopies; > > 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. 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