LLVM API Documentation
00001 //===-- SimpleRegisterCoalescing.cpp - Register Coalescing ----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a simple register coalescing pass that attempts to 00011 // aggressively coalesce every register copy that it can. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "regcoalescing" 00016 #include "SimpleRegisterCoalescing.h" 00017 #include "VirtRegMap.h" 00018 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 00019 #include "llvm/Value.h" 00020 #include "llvm/CodeGen/MachineFrameInfo.h" 00021 #include "llvm/CodeGen/MachineInstr.h" 00022 #include "llvm/CodeGen/MachineLoopInfo.h" 00023 #include "llvm/CodeGen/MachineRegisterInfo.h" 00024 #include "llvm/CodeGen/Passes.h" 00025 #include "llvm/CodeGen/RegisterCoalescer.h" 00026 #include "llvm/Target/TargetInstrInfo.h" 00027 #include "llvm/Target/TargetMachine.h" 00028 #include "llvm/Target/TargetOptions.h" 00029 #include "llvm/Support/CommandLine.h" 00030 #include "llvm/Support/Debug.h" 00031 #include "llvm/Support/ErrorHandling.h" 00032 #include "llvm/Support/raw_ostream.h" 00033 #include "llvm/ADT/SmallSet.h" 00034 #include "llvm/ADT/Statistic.h" 00035 #include "llvm/ADT/STLExtras.h" 00036 #include <algorithm> 00037 #include <cmath> 00038 using namespace llvm; 00039 00040 STATISTIC(numJoins , "Number of interval joins performed"); 00041 STATISTIC(numCrossRCs , "Number of cross class joins performed"); 00042 STATISTIC(numCommutes , "Number of instruction commuting performed"); 00043 STATISTIC(numExtends , "Number of copies extended"); 00044 STATISTIC(NumReMats , "Number of instructions re-materialized"); 00045 STATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); 00046 STATISTIC(numAborts , "Number of times interval joining aborted"); 00047 STATISTIC(numDeadValNo, "Number of valno def marked dead"); 00048 00049 char SimpleRegisterCoalescing::ID = 0; 00050 static cl::opt<bool> 00051 EnableJoining("join-liveintervals", 00052 cl::desc("Coalesce copies (default=true)"), 00053 cl::init(true)); 00054 00055 static cl::opt<bool> 00056 NewHeuristic("new-coalescer-heuristic", 00057 cl::desc("Use new coalescer heuristic"), 00058 cl::init(false), cl::Hidden); 00059 00060 static cl::opt<bool> 00061 DisableCrossClassJoin("disable-cross-class-join", 00062 cl::desc("Avoid coalescing cross register class copies"), 00063 cl::init(false), cl::Hidden); 00064 00065 static cl::opt<bool> 00066 PhysJoinTweak("tweak-phys-join-heuristics", 00067 cl::desc("Tweak heuristics for joining phys reg with vr"), 00068 cl::init(false), cl::Hidden); 00069 00070 static RegisterPass<SimpleRegisterCoalescing> 00071 X("simple-register-coalescing", "Simple Register Coalescing"); 00072 00073 // Declare that we implement the RegisterCoalescer interface 00074 static RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X); 00075 00076 const PassInfo *const llvm::SimpleRegisterCoalescingID = &X; 00077 00078 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const { 00079 AU.setPreservesCFG(); 00080 AU.addRequired<LiveIntervals>(); 00081 AU.addPreserved<LiveIntervals>(); 00082 AU.addRequired<MachineLoopInfo>(); 00083 AU.addPreserved<MachineLoopInfo>(); 00084 AU.addPreservedID(MachineDominatorsID); 00085 if (StrongPHIElim) 00086 AU.addPreservedID(StrongPHIEliminationID); 00087 else 00088 AU.addPreservedID(PHIEliminationID); 00089 AU.addPreservedID(TwoAddressInstructionPassID); 00090 MachineFunctionPass::getAnalysisUsage(AU); 00091 } 00092 00093 /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 00094 /// being the source and IntB being the dest, thus this defines a value number 00095 /// in IntB. If the source value number (in IntA) is defined by a copy from B, 00096 /// see if we can merge these two pieces of B into a single value number, 00097 /// eliminating a copy. For example: 00098 /// 00099 /// A3 = B0 00100 /// ... 00101 /// B1 = A3 <- this copy 00102 /// 00103 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 00104 /// value number to be replaced with B0 (which simplifies the B liveinterval). 00105 /// 00106 /// This returns true if an interval was modified. 00107 /// 00108 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, 00109 LiveInterval &IntB, 00110 MachineInstr *CopyMI) { 00111 unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); 00112 00113 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 00114 // the example above. 00115 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 00116 assert(BLR != IntB.end() && "Live range not found!"); 00117 VNInfo *BValNo = BLR->valno; 00118 00119 // Get the location that B is defined at. Two options: either this value has 00120 // an unknown definition point or it is defined at CopyIdx. If unknown, we 00121 // can't process it. 00122 if (!BValNo->getCopy()) return false; 00123 assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 00124 00125 // AValNo is the value number in A that defines the copy, A3 in the example. 00126 unsigned CopyUseIdx = li_->getUseIndex(CopyIdx); 00127 LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 00128 assert(ALR != IntA.end() && "Live range not found!"); 00129 VNInfo *AValNo = ALR->valno; 00130 // If it's re-defined by an early clobber somewhere in the live range, then 00131 // it's not safe to eliminate the copy. FIXME: This is a temporary workaround. 00132 // See PR3149: 00133 // 172 %ECX<def> = MOV32rr %reg1039<kill> 00134 // 180 INLINEASM <es:subl $5,$1 00135 // sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9, %EAX<kill>, 00136 // 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0 00137 // 188 %EAX<def> = MOV32rr %EAX<kill> 00138 // 196 %ECX<def> = MOV32rr %ECX<kill> 00139 // 204 %ECX<def> = MOV32rr %ECX<kill> 00140 // 212 %EAX<def> = MOV32rr %EAX<kill> 00141 // 220 %EAX<def> = MOV32rr %EAX 00142 // 228 %reg1039<def> = MOV32rr %ECX<kill> 00143 // The early clobber operand ties ECX input to the ECX def. 00144 // 00145 // The live interval of ECX is represented as this: 00146 // %reg20,inf = [46,47:1)[174,230:0) 0@174-(230) 1@46-(47) 00147 // The coalescer has no idea there was a def in the middle of [174,230]. 00148 if (AValNo->hasRedefByEC()) 00149 return false; 00150 00151 // If AValNo is defined as a copy from IntB, we can potentially process this. 00152 // Get the instruction that defines this value number. 00153 unsigned SrcReg = li_->getVNInfoSourceReg(AValNo); 00154 if (!SrcReg) return false; // Not defined by a copy. 00155 00156 // If the value number is not defined by a copy instruction, ignore it. 00157 00158 // If the source register comes from an interval other than IntB, we can't 00159 // handle this. 00160 if (SrcReg != IntB.reg) return false; 00161 00162 // Get the LiveRange in IntB that this value number starts with. 00163 LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1); 00164 assert(ValLR != IntB.end() && "Live range not found!"); 00165 00166 // Make sure that the end of the live range is inside the same block as 00167 // CopyMI. 00168 MachineInstr *ValLREndInst = li_->getInstructionFromIndex(ValLR->end-1); 00169 if (!ValLREndInst || 00170 ValLREndInst->getParent() != CopyMI->getParent()) return false; 00171 00172 // Okay, we now know that ValLR ends in the same block that the CopyMI 00173 // live-range starts. If there are no intervening live ranges between them in 00174 // IntB, we can merge them. 00175 if (ValLR+1 != BLR) return false; 00176 00177 // If a live interval is a physical register, conservatively check if any 00178 // of its sub-registers is overlapping the live interval of the virtual 00179 // register. If so, do not coalesce. 00180 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) && 00181 *tri_->getSubRegisters(IntB.reg)) { 00182 for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) 00183 if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) { 00184 DOUT << "Interfere with sub-register "; 00185 DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); 00186 return false; 00187 } 00188 } 00189 00190 DOUT << "\nExtending: "; IntB.print(DOUT, tri_); 00191 00192 unsigned FillerStart = ValLR->end, FillerEnd = BLR->start; 00193 // We are about to delete CopyMI, so need to remove it as the 'instruction 00194 // that defines this value #'. Update the the valnum with the new defining 00195 // instruction #. 00196 BValNo->def = FillerStart; 00197 BValNo->setCopy(0); 00198 00199 // Okay, we can merge them. We need to insert a new liverange: 00200 // [ValLR.end, BLR.begin) of either value number, then we merge the 00201 // two value numbers. 00202 IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 00203 00204 // If the IntB live range is assigned to a physical register, and if that 00205 // physreg has sub-registers, update their live intervals as well. 00206 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 00207 for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { 00208 LiveInterval &SRLI = li_->getInterval(*SR); 00209 SRLI.addRange(LiveRange(FillerStart, FillerEnd, 00210 SRLI.getNextValue(FillerStart, 0, true, 00211 li_->getVNInfoAllocator()))); 00212 } 00213 } 00214 00215 // Okay, merge "B1" into the same value number as "B0". 00216 if (BValNo != ValLR->valno) { 00217 IntB.addKills(ValLR->valno, BValNo->kills); 00218 IntB.MergeValueNumberInto(BValNo, ValLR->valno); 00219 } 00220 DOUT << " result = "; IntB.print(DOUT, tri_); 00221 DOUT << "\n"; 00222 00223 // If the source instruction was killing the source register before the 00224 // merge, unset the isKill marker given the live range has been extended. 00225 int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 00226 if (UIdx != -1) { 00227 ValLREndInst->getOperand(UIdx).setIsKill(false); 00228 IntB.removeKill(ValLR->valno, FillerStart); 00229 } 00230 00231 // If the copy instruction was killing the destination register before the 00232 // merge, find the last use and trim the live range. That will also add the 00233 // isKill marker. 00234 if (CopyMI->killsRegister(IntA.reg)) 00235 TrimLiveIntervalToLastUse(CopyUseIdx, CopyMI->getParent(), IntA, ALR); 00236 00237 ++numExtends; 00238 return true; 00239 } 00240 00241 /// HasOtherReachingDefs - Return true if there are definitions of IntB 00242 /// other than BValNo val# that can reach uses of AValno val# of IntA. 00243 bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA, 00244 LiveInterval &IntB, 00245 VNInfo *AValNo, 00246 VNInfo *BValNo) { 00247 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 00248 AI != AE; ++AI) { 00249 if (AI->valno != AValNo) continue; 00250 LiveInterval::Ranges::iterator BI = 00251 std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 00252 if (BI != IntB.ranges.begin()) 00253 --BI; 00254 for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 00255 if (BI->valno == BValNo) 00256 continue; 00257 if (BI->start <= AI->start && BI->end > AI->start) 00258 return true; 00259 if (BI->start > AI->start && BI->start < AI->end) 00260 return true; 00261 } 00262 } 00263 return false; 00264 } 00265 00266 /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with IntA 00267 /// being the source and IntB being the dest, thus this defines a value number 00268 /// in IntB. If the source value number (in IntA) is defined by a commutable 00269 /// instruction and its other operand is coalesced to the copy dest register, 00270 /// see if we can transform the copy into a noop by commuting the definition. For 00271 /// example, 00272 /// 00273 /// A3 = op A2 B0<kill> 00274 /// ... 00275 /// B1 = A3 <- this copy 00276 /// ... 00277 /// = op A3 <- more uses 00278 /// 00279 /// ==> 00280 /// 00281 /// B2 = op B0 A2<kill> 00282 /// ... 00283 /// B1 = B2 <- now an identify copy 00284 /// ... 00285 /// = op B2 <- more uses 00286 /// 00287 /// This returns true if an interval was modified. 00288 /// 00289 bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, 00290 LiveInterval &IntB, 00291 MachineInstr *CopyMI) { 00292 unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); 00293 00294 // FIXME: For now, only eliminate the copy by commuting its def when the 00295 // source register is a virtual register. We want to guard against cases 00296 // where the copy is a back edge copy and commuting the def lengthen the 00297 // live interval of the source register to the entire loop. 00298 if (TargetRegisterInfo::isPhysicalRegister(IntA.reg)) 00299 return false; 00300 00301 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 00302 // the example above. 00303 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 00304 assert(BLR != IntB.end() && "Live range not found!"); 00305 VNInfo *BValNo = BLR->valno; 00306 00307 // Get the location that B is defined at. Two options: either this value has 00308 // an unknown definition point or it is defined at CopyIdx. If unknown, we 00309 // can't process it. 00310 if (!BValNo->getCopy()) return false; 00311 assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 00312 00313 // AValNo is the value number in A that defines the copy, A3 in the example. 00314 LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1); 00315 assert(ALR != IntA.end() && "Live range not found!"); 00316 VNInfo *AValNo = ALR->valno; 00317 // If other defs can reach uses of this def, then it's not safe to perform 00318 // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be 00319 // tested? 00320 if (AValNo->isPHIDef() || !AValNo->isDefAccurate() || 00321 AValNo->isUnused() || AValNo->hasPHIKill()) 00322 return false; 00323 MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def); 00324 const TargetInstrDesc &TID = DefMI->getDesc(); 00325 if (!TID.isCommutable()) 00326 return false; 00327 // If DefMI is a two-address instruction then commuting it will change the 00328 // destination register. 00329 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 00330 assert(DefIdx != -1); 00331 unsigned UseOpIdx; 00332 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 00333 return false; 00334 unsigned Op1, Op2, NewDstIdx; 00335 if (!tii_->findCommutedOpIndices(DefMI, Op1, Op2)) 00336 return false; 00337 if (Op1 == UseOpIdx) 00338 NewDstIdx = Op2; 00339 else if (Op2 == UseOpIdx) 00340 NewDstIdx = Op1; 00341 else 00342 return false; 00343 00344 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 00345 unsigned NewReg = NewDstMO.getReg(); 00346 if (NewReg != IntB.reg || !NewDstMO.isKill()) 00347 return false; 00348 00349 // Make sure there are no other definitions of IntB that would reach the 00350 // uses which the new definition can reach. 00351 if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 00352 return false; 00353 00354 // If some of the uses of IntA.reg is already coalesced away, return false. 00355 // It's not possible to determine whether it's safe to perform the coalescing. 00356 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg), 00357 UE = mri_->use_end(); UI != UE; ++UI) { 00358 MachineInstr *UseMI = &*UI; 00359 unsigned UseIdx = li_->getInstructionIndex(UseMI); 00360 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 00361 if (ULR == IntA.end()) 00362 continue; 00363 if (ULR->valno == AValNo && JoinedCopies.count(UseMI)) 00364 return false; 00365 } 00366 00367 // At this point we have decided that it is legal to do this 00368 // transformation. Start by commuting the instruction. 00369 MachineBasicBlock *MBB = DefMI->getParent(); 00370 MachineInstr *NewMI = tii_->commuteInstruction(DefMI); 00371 if (!NewMI) 00372 return false; 00373 if (NewMI != DefMI) { 00374 li_->ReplaceMachineInstrInMaps(DefMI, NewMI); 00375 MBB->insert(DefMI, NewMI); 00376 MBB->erase(DefMI); 00377 } 00378 unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 00379 NewMI->getOperand(OpIdx).setIsKill(); 00380 00381 bool BHasPHIKill = BValNo->hasPHIKill(); 00382 SmallVector<VNInfo*, 4> BDeadValNos; 00383 VNInfo::KillSet BKills; 00384 std::map<unsigned, unsigned> BExtend; 00385 00386 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 00387 // A = or A, B 00388 // ... 00389 // B = A 00390 // ... 00391 // C = A<kill> 00392 // ... 00393 // = B 00394 // 00395 // then do not add kills of A to the newly created B interval. 00396 bool Extended = BLR->end > ALR->end && ALR->end != ALR->start; 00397 if (Extended) 00398 BExtend[ALR->end] = BLR->end; 00399 00400 // Update uses of IntA of the specific Val# with IntB. 00401 bool BHasSubRegs = false; 00402 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) 00403 BHasSubRegs = *tri_->getSubRegisters(IntB.reg); 00404 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg), 00405 UE = mri_->use_end(); UI != UE;) { 00406 MachineOperand &UseMO = UI.getOperand(); 00407 MachineInstr *UseMI = &*UI; 00408 ++UI; 00409 if (JoinedCopies.count(UseMI)) 00410 continue; 00411 unsigned UseIdx = li_->getInstructionIndex(UseMI); 00412 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 00413 if (ULR == IntA.end() || ULR->valno != AValNo) 00414 continue; 00415 UseMO.setReg(NewReg); 00416 if (UseMI == CopyMI) 00417 continue; 00418 if (UseMO.isKill()) { 00419 if (Extended) 00420 UseMO.setIsKill(false); 00421 else 00422 BKills.push_back(VNInfo::KillInfo(false, li_->getUseIndex(UseIdx)+1)); 00423 } 00424 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 00425 if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) 00426 continue; 00427 if (DstReg == IntB.reg) { 00428 // This copy will become a noop. If it's defining a new val#, 00429 // remove that val# as well. However this live range is being 00430 // extended to the end of the existing live range defined by the copy. 00431 unsigned DefIdx = li_->getDefIndex(UseIdx); 00432 const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx); 00433 BHasPHIKill |= DLR->valno->hasPHIKill(); 00434 assert(DLR->valno->def == DefIdx); 00435 BDeadValNos.push_back(DLR->valno); 00436 BExtend[DLR->start] = DLR->end; 00437 JoinedCopies.insert(UseMI); 00438 // If this is a kill but it's going to be removed, the last use 00439 // of the same val# is the new kill. 00440 if (UseMO.isKill()) 00441 BKills.pop_back(); 00442 } 00443 } 00444 00445 // We need to insert a new liverange: [ALR.start, LastUse). It may be we can 00446 // simply extend BLR if CopyMI doesn't end the range. 00447 DOUT << "\nExtending: "; IntB.print(DOUT, tri_); 00448 00449 // Remove val#'s defined by copies that will be coalesced away. 00450 for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i) { 00451 VNInfo *DeadVNI = BDeadValNos[i]; 00452 if (BHasSubRegs) { 00453 for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { 00454 LiveInterval &SRLI = li_->getInterval(*SR); 00455 const LiveRange *SRLR = SRLI.getLiveRangeContaining(DeadVNI->def); 00456 SRLI.removeValNo(SRLR->valno); 00457 } 00458 } 00459 IntB.removeValNo(BDeadValNos[i]); 00460 } 00461 00462 // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 00463 // is updated. Kills are also updated. 00464 VNInfo *ValNo = BValNo; 00465 ValNo->def = AValNo->def; 00466 ValNo->setCopy(0); 00467 for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) { 00468 unsigned Kill = ValNo->kills[j].killIdx; 00469 if (Kill != BLR->end) 00470 BKills.push_back(VNInfo::KillInfo(ValNo->kills[j].isPHIKill, Kill)); 00471 } 00472 ValNo->kills.clear(); 00473 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 00474 AI != AE; ++AI) { 00475 if (AI->valno != AValNo) continue; 00476 unsigned End = AI->end; 00477 std::map<unsigned, unsigned>::iterator EI = BExtend.find(End); 00478 if (EI != BExtend.end()) 00479 End = EI->second; 00480 IntB.addRange(LiveRange(AI->start, End, ValNo)); 00481 00482 // If the IntB live range is assigned to a physical register, and if that 00483 // physreg has sub-registers, update their live intervals as well. 00484 if (BHasSubRegs) { 00485 for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { 00486 LiveInterval &SRLI = li_->getInterval(*SR); 00487 SRLI.MergeInClobberRange(AI->start, End, li_->getVNInfoAllocator()); 00488 } 00489 } 00490 } 00491 IntB.addKills(ValNo, BKills); 00492 ValNo->setHasPHIKill(BHasPHIKill); 00493 00494 DOUT << " result = "; IntB.print(DOUT, tri_); 00495 DOUT << "\n"; 00496 00497 DOUT << "\nShortening: "; IntA.print(DOUT, tri_); 00498 IntA.removeValNo(AValNo); 00499 DOUT << " result = "; IntA.print(DOUT, tri_); 00500 DOUT << "\n"; 00501 00502 ++numCommutes; 00503 return true; 00504 } 00505 00506 /// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply 00507 /// fallthoughs to SuccMBB. 00508 static bool isSameOrFallThroughBB(MachineBasicBlock *MBB, 00509 MachineBasicBlock *SuccMBB, 00510 const TargetInstrInfo *tii_) { 00511 if (MBB == SuccMBB) 00512 return true; 00513 MachineBasicBlock *TBB = 0, *FBB = 0; 00514 SmallVector<MachineOperand, 4> Cond; 00515 return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB && 00516 MBB->isSuccessor(SuccMBB); 00517 } 00518 00519 /// removeRange - Wrapper for LiveInterval::removeRange. This removes a range 00520 /// from a physical register live interval as well as from the live intervals 00521 /// of its sub-registers. 00522 static void removeRange(LiveInterval &li, unsigned Start, unsigned End, 00523 LiveIntervals *li_, const TargetRegisterInfo *tri_) { 00524 li.removeRange(Start, End, true); 00525 if (TargetRegisterInfo::isPhysicalRegister(li.reg)) { 00526 for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { 00527 if (!li_->hasInterval(*SR)) 00528 continue; 00529 LiveInterval &sli = li_->getInterval(*SR); 00530 unsigned RemoveStart = Start; 00531 unsigned RemoveEnd = Start; 00532 while (RemoveEnd != End) { 00533 LiveInterval::iterator LR = sli.FindLiveRangeContaining(RemoveStart); 00534 if (LR == sli.end()) 00535 break; 00536 RemoveEnd = (LR->end < End) ? LR->end : End; 00537 sli.removeRange(RemoveStart, RemoveEnd, true); 00538 RemoveStart = RemoveEnd; 00539 } 00540 } 00541 } 00542 } 00543 00544 /// TrimLiveIntervalToLastUse - If there is a last use in the same basic block 00545 /// as the copy instruction, trim the live interval to the last use and return 00546 /// true. 00547 bool 00548 SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(unsigned CopyIdx, 00549 MachineBasicBlock *CopyMBB, 00550 LiveInterval &li, 00551 const LiveRange *LR) { 00552 unsigned MBBStart = li_->getMBBStartIdx(CopyMBB); 00553 unsigned LastUseIdx; 00554 MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg, 00555 LastUseIdx); 00556 if (LastUse) { 00557 MachineInstr *LastUseMI = LastUse->getParent(); 00558 if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) { 00559 // r1024 = op 00560 // ... 00561 // BB1: 00562 // = r1024 00563 // 00564 // BB2: 00565 // r1025<dead> = r1024<kill> 00566 if (MBBStart < LR->end) 00567 removeRange(li, MBBStart, LR->end, li_, tri_); 00568 return true; 00569 } 00570 00571 // There are uses before the copy, just shorten the live range to the end 00572 // of last use. 00573 LastUse->setIsKill(); 00574 removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_); 00575 li.addKill(LR->valno, LastUseIdx+1, false); 00576 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 00577 if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && 00578 DstReg == li.reg) { 00579 // Last use is itself an identity code. 00580 int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_); 00581 LastUseMI->getOperand(DeadIdx).setIsDead(); 00582 } 00583 return true; 00584 } 00585 00586 // Is it livein? 00587 if (LR->start <= MBBStart && LR->end > MBBStart) { 00588 if (LR->start == 0) { 00589 assert(TargetRegisterInfo::isPhysicalRegister(li.reg)); 00590 // Live-in to the function but dead. Remove it from entry live-in set. 00591 mf_->begin()->removeLiveIn(li.reg); 00592 } 00593 // FIXME: Shorten intervals in BBs that reaches this BB. 00594 } 00595 00596 return false; 00597 } 00598 00599 /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial 00600 /// computation, replace the copy by rematerialize the definition. 00601 bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt, 00602 unsigned DstReg, 00603 unsigned DstSubIdx, 00604 MachineInstr *CopyMI) { 00605 unsigned CopyIdx = li_->getUseIndex(li_->getInstructionIndex(CopyMI)); 00606 LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 00607 assert(SrcLR != SrcInt.end() && "Live range not found!"); 00608 VNInfo *ValNo = SrcLR->valno; 00609 // If other defs can reach uses of this def, then it's not safe to perform 00610 // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be 00611 // tested? 00612 if (ValNo->isPHIDef() || !ValNo->isDefAccurate() || 00613 ValNo->isUnused() || ValNo->hasPHIKill()) 00614 return false; 00615 MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def); 00616 const TargetInstrDesc &TID = DefMI->getDesc(); 00617 if (!TID.isAsCheapAsAMove()) 00618 return false; 00619 if (!DefMI->getDesc().isRematerializable() || 00620 !tii_->isTriviallyReMaterializable(DefMI)) 00621 return false; 00622 bool SawStore = false; 00623 if (!DefMI->isSafeToMove(tii_, SawStore)) 00624 return false; 00625 if (TID.getNumDefs() != 1) 00626 return false; 00627 if (DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { 00628 // Make sure the copy destination register class fits the instruction 00629 // definition register class. The mismatch can happen as a result of earlier 00630 // extract_subreg, insert_subreg, subreg_to_reg coalescing. 00631 const TargetRegisterClass *RC = TID.OpInfo[0].getRegClass(tri_); 00632 if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 00633 if (mri_->getRegClass(DstReg) != RC) 00634 return false; 00635 } else if (!RC->contains(DstReg)) 00636 return false; 00637 } 00638 00639 // If destination register has a sub-register index on it, make sure it mtches 00640 // the instruction register class. 00641 if (DstSubIdx) { 00642 const TargetInstrDesc &TID = DefMI->getDesc(); 00643 if (TID.getNumDefs() != 1) 00644 return false; 00645 const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg); 00646 const TargetRegisterClass *DstSubRC = 00647 DstRC->getSubRegisterRegClass(DstSubIdx); 00648 const TargetRegisterClass *DefRC = TID.OpInfo[0].getRegClass(tri_); 00649 if (DefRC == DstRC) 00650 DstSubIdx = 0; 00651 else if (DefRC != DstSubRC) 00652 return false; 00653 } 00654 00655 unsigned DefIdx = li_->getDefIndex(CopyIdx); 00656 const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx); 00657 DLR->valno->setCopy(0); 00658 // Don't forget to update sub-register intervals. 00659 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 00660 for (const unsigned* SR = tri_->getSubRegisters(DstReg); *SR; ++SR) { 00661 if (!li_->hasInterval(*SR)) 00662 continue; 00663 DLR = li_->getInterval(*SR).getLiveRangeContaining(DefIdx); 00664 if (DLR && DLR->valno->getCopy() == CopyMI) 00665 DLR->valno->setCopy(0); 00666 } 00667 } 00668 00669 // If copy kills the source register, find the last use and propagate 00670 // kill. 00671 bool checkForDeadDef = false; 00672 MachineBasicBlock *MBB = CopyMI->getParent(); 00673 if (CopyMI->killsRegister(SrcInt.reg)) 00674 if (!TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR)) { 00675 checkForDeadDef = true; 00676 } 00677 00678 MachineBasicBlock::iterator MII = next(MachineBasicBlock::iterator(CopyMI)); 00679 tii_->reMaterialize(*MBB, MII, DstReg, DstSubIdx, DefMI); 00680 MachineInstr *NewMI = prior(MII); 00681 00682 if (checkForDeadDef) { 00683 // PR4090 fix: Trim interval failed because there was no use of the 00684 // source interval in this MBB. If the def is in this MBB too then we 00685 // should mark it dead: 00686 if (DefMI->getParent() == MBB) { 00687 DefMI->addRegisterDead(SrcInt.reg, tri_); 00688 SrcLR->end = SrcLR->start + 1; 00689 } 00690 } 00691 00692 // CopyMI may have implicit operands, transfer them over to the newly 00693 // rematerialized instruction. And update implicit def interval valnos. 00694 for (unsigned i = CopyMI->getDesc().getNumOperands(), 00695 e = CopyMI->getNumOperands(); i != e; ++i) { 00696 MachineOperand &MO = CopyMI->getOperand(i); 00697 if (MO.isReg() && MO.isImplicit()) 00698 NewMI->addOperand(MO); 00699 if (MO.isDef() && li_->hasInterval(MO.getReg())) { 00700 unsigned Reg = MO.getReg(); 00701 DLR = li_->getInterval(Reg).getLiveRangeContaining(DefIdx); 00702 if (DLR && DLR->valno->getCopy() == CopyMI) 00703 DLR->valno->setCopy(0); 00704 } 00705 } 00706 00707 li_->ReplaceMachineInstrInMaps(CopyMI, NewMI); 00708 CopyMI->eraseFromParent(); 00709 ReMatCopies.insert(CopyMI); 00710 ReMatDefs.insert(DefMI); 00711 ++NumReMats; 00712 return true; 00713 } 00714 00715 /// isBackEdgeCopy - Returns true if CopyMI is a back edge copy. 00716 /// 00717 bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI, 00718 unsigned DstReg) const { 00719 MachineBasicBlock *MBB = CopyMI->getParent(); 00720 const MachineLoop *L = loopInfo->getLoopFor(MBB); 00721 if (!L) 00722 return false; 00723 if (MBB != L->getLoopLatch()) 00724 return false; 00725 00726 LiveInterval &LI = li_->getInterval(DstReg); 00727 unsigned DefIdx = li_->getInstructionIndex(CopyMI); 00728 LiveInterval::const_iterator DstLR = 00729 LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx)); 00730 if (DstLR == LI.end()) 00731 return false; 00732 if (DstLR->valno->kills.size() == 1 && DstLR->valno->kills[0].isPHIKill) 00733 return true; 00734 return false; 00735 } 00736 00737 /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 00738 /// update the subregister number if it is not zero. If DstReg is a 00739 /// physical register and the existing subregister number of the def / use 00740 /// being updated is not zero, make sure to set it to the correct physical 00741 /// subregister. 00742 void 00743 SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg, 00744 unsigned SubIdx) { 00745 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 00746 if (DstIsPhys && SubIdx) { 00747 // Figure out the real physical register we are updating with. 00748 DstReg = tri_->getSubReg(DstReg, SubIdx); 00749 SubIdx = 0; 00750 } 00751 00752 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg), 00753 E = mri_->reg_end(); I != E; ) { 00754 MachineOperand &O = I.getOperand(); 00755 MachineInstr *UseMI = &*I; 00756 ++I; 00757 unsigned OldSubIdx = O.getSubReg(); 00758 if (DstIsPhys) { 00759 unsigned UseDstReg = DstReg; 00760 if (OldSubIdx) 00761 UseDstReg = tri_->getSubReg(DstReg, OldSubIdx); 00762 00763 unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx; 00764 if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg, 00765 CopySrcSubIdx, CopyDstSubIdx) && 00766 CopySrcReg != CopyDstReg && 00767 CopySrcReg == SrcReg && CopyDstReg != UseDstReg) { 00768 // If the use is a copy and it won't be coalesced away, and its source 00769 // is defined by a trivial computation, try to rematerialize it instead. 00770 if (ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg, 00771 CopyDstSubIdx, UseMI)) 00772 continue; 00773 } 00774 00775 O.setReg(UseDstReg); 00776 O.setSubReg(0); 00777 continue; 00778 } 00779 00780 // Sub-register indexes goes from small to large. e.g. 00781 // RAX: 1 -> AL, 2 -> AX, 3 -> EAX 00782 // EAX: 1 -> AL, 2 -> AX 00783 // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose 00784 // sub-register 2 is also AX. 00785 if (SubIdx && OldSubIdx && SubIdx != OldSubIdx) 00786 assert(OldSubIdx < SubIdx && "Conflicting sub-register index!"); 00787 else if (SubIdx) 00788 O.setSubReg(SubIdx); 00789 // Remove would-be duplicated kill marker. 00790 if (O.isKill() && UseMI->killsRegister(DstReg)) 00791 O.setIsKill(false); 00792 O.setReg(DstReg); 00793 00794 // After updating the operand, check if the machine instruction has 00795 // become a copy. If so, update its val# information. 00796 if (JoinedCopies.count(UseMI)) 00797 continue; 00798 00799 const TargetInstrDesc &TID = UseMI->getDesc(); 00800 unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx; 00801 if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 && 00802 tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg, 00803 CopySrcSubIdx, CopyDstSubIdx) && 00804 CopySrcReg != CopyDstReg && 00805 (TargetRegisterInfo::isVirtualRegister(CopyDstReg) || 00806 allocatableRegs_[CopyDstReg])) { 00807 LiveInterval &LI = li_->getInterval(CopyDstReg); 00808 unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(UseMI)); 00809 if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) { 00810 if (DLR->valno->def == DefIdx) 00811 DLR->valno->setCopy(UseMI); 00812 } 00813 } 00814 } 00815 } 00816 00817 /// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate 00818 /// due to live range lengthening as the result of coalescing. 00819 void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg, 00820 LiveInterval &LI) { 00821 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), 00822 UE = mri_->use_end(); UI != UE; ++UI) { 00823 MachineOperand &UseMO = UI.getOperand(); 00824 if (!UseMO.isKill()) 00825 continue; 00826 MachineInstr *UseMI = UseMO.getParent(); 00827 unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI)); 00828 const LiveRange *LR = LI.getLiveRangeContaining(UseIdx); 00829 if (!LR || !LI.isKill(LR->valno, UseIdx+1)) { 00830 if (LR->valno->def != UseIdx+1) { 00831 // Interesting problem. After coalescing reg1027's def and kill are both 00832 // at the same point: %reg1027,0.000000e+00 = [56,814:0) 0@70-(814) 00833 // 00834 // bb5: 00835 // 60 %reg1027<def> = t2MOVr %reg1027, 14, %reg0, %reg0 00836 // 68 %reg1027<def> = t2LDRi12 %reg1027<kill>, 8, 14, %reg0 00837 // 76 t2CMPzri %reg1038<kill,undef>, 0, 14, %reg0, %CPSR<imp-def> 00838 // 84 %reg1027<def> = t2MOVr %reg1027, 14, %reg0, %reg0 00839 // 96 t2Bcc mbb<bb5,0x2030910>, 1, %CPSR<kill> 00840 // 00841 // Do not remove the kill marker on t2LDRi12. 00842 UseMO.setIsKill(false); 00843 } 00844 } 00845 } 00846 } 00847 00848 /// removeIntervalIfEmpty - Check if the live interval of a physical register 00849 /// is empty, if so remove it and also remove the empty intervals of its 00850 /// sub-registers. Return true if live interval is removed. 00851 static bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_, 00852 const TargetRegisterInfo *tri_) { 00853 if (li.empty()) { 00854 if (TargetRegisterInfo::isPhysicalRegister(li.reg)) 00855 for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { 00856 if (!li_->hasInterval(*SR)) 00857 continue; 00858 LiveInterval &sli = li_->getInterval(*SR); 00859 if (sli.empty()) 00860 li_->removeInterval(*SR); 00861 } 00862 li_->removeInterval(li.reg); 00863 return true; 00864 } 00865 return false; 00866 } 00867 00868 /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy. 00869 /// Return true if live interval is removed. 00870 bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li, 00871 MachineInstr *CopyMI) { 00872 unsigned CopyIdx = li_->getInstructionIndex(CopyMI); 00873 LiveInterval::iterator MLR = 00874 li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx)); 00875 if (MLR == li.end()) 00876 return false; // Already removed by ShortenDeadCopySrcLiveRange. 00877 unsigned RemoveStart = MLR->start; 00878 unsigned RemoveEnd = MLR->end; 00879 unsigned DefIdx = li_->getDefIndex(CopyIdx); 00880 // Remove the liverange that's defined by this. 00881 if (RemoveStart == DefIdx && RemoveEnd == DefIdx+1) { 00882 removeRange(li, RemoveStart, RemoveEnd, li_, tri_); 00883 return removeIntervalIfEmpty(li, li_, tri_); 00884 } 00885 return false; 00886 } 00887 00888 /// RemoveDeadDef - If a def of a live interval is now determined dead, remove 00889 /// the val# it defines. If the live interval becomes empty, remove it as well. 00890 bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li, 00891 MachineInstr *DefMI) { 00892 unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(DefMI)); 00893 LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx); 00894 if (DefIdx != MLR->valno->def) 00895 return false; 00896 li.removeValNo(MLR->valno); 00897 return removeIntervalIfEmpty(li, li_, tri_); 00898 } 00899 00900 /// PropagateDeadness - Propagate the dead marker to the instruction which 00901 /// defines the val#. 00902 static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI, 00903 unsigned &LRStart, LiveIntervals *li_, 00904 const TargetRegisterInfo* tri_) { 00905 MachineInstr *DefMI = 00906 li_->getInstructionFromIndex(li_->getDefIndex(LRStart)); 00907 if (DefMI && DefMI != CopyMI) { 00908 int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false); 00909 if (DeadIdx != -1) 00910 DefMI->getOperand(DeadIdx).setIsDead(); 00911 else 00912 DefMI->addOperand(MachineOperand::CreateReg(li.reg, 00913 true, true, false, true)); 00914 ++LRStart; 00915 } 00916 } 00917 00918 /// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially 00919 /// extended by a dead copy. Mark the last use (if any) of the val# as kill as 00920 /// ends the live range there. If there isn't another use, then this live range 00921 /// is dead. Return true if live interval is removed. 00922 bool 00923 SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li, 00924 MachineInstr *CopyMI) { 00925 unsigned CopyIdx = li_->getInstructionIndex(CopyMI); 00926 if (CopyIdx == 0) { 00927 // FIXME: special case: function live in. It can be a general case if the 00928 // first instruction index starts at > 0 value. 00929 assert(TargetRegisterInfo::isPhysicalRegister(li.reg)); 00930 // Live-in to the function but dead. Remove it from entry live-in set. 00931 if (mf_->begin()->isLiveIn(li.reg)) 00932 mf_->begin()->removeLiveIn(li.reg); 00933 const LiveRange *LR = li.getLiveRangeContaining(CopyIdx); 00934 removeRange(li, LR->start, LR->end, li_, tri_); 00935 return removeIntervalIfEmpty(li, li_, tri_); 00936 } 00937 00938 LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx-1); 00939 if (LR == li.end()) 00940 // Livein but defined by a phi. 00941 return false; 00942 00943 unsigned RemoveStart = LR->start; 00944 unsigned RemoveEnd = li_->getDefIndex(CopyIdx)+1; 00945 if (LR->end > RemoveEnd) 00946 // More uses past this copy? Nothing to do. 00947 return false; 00948 00949 // If there is a last use in the same bb, we can't remove the live range. 00950 // Shorten the live interval and return. 00951 MachineBasicBlock *CopyMBB = CopyMI->getParent(); 00952 if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR)) 00953 return false; 00954 00955 // There are other kills of the val#. Nothing to do. 00956 if (!li.isOnlyLROfValNo(LR)) 00957 return false; 00958 00959 MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart); 00960 if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_)) 00961 // If the live range starts in another mbb and the copy mbb is not a fall 00962 // through mbb, then we can only cut the range from the beginning of the 00963 // copy mbb. 00964 RemoveStart = li_->getMBBStartIdx(CopyMBB) + 1; 00965 00966 if (LR->valno->def == RemoveStart) { 00967 // If the def MI defines the val# and this copy is the only kill of the 00968 // val#, then propagate the dead marker. 00969 PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_); 00970 ++numDeadValNo; 00971 00972 if (li.isKill(LR->valno, RemoveEnd)) 00973 li.removeKill(LR->valno, RemoveEnd); 00974 } 00975 00976 removeRange(li, RemoveStart, RemoveEnd, li_, tri_); 00977 return removeIntervalIfEmpty(li, li_, tri_); 00978 } 00979 00980 /// CanCoalesceWithImpDef - Returns true if the specified copy instruction 00981 /// from an implicit def to another register can be coalesced away. 00982 bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI, 00983 LiveInterval &li, 00984 LiveInterval &ImpLi) const{ 00985 if (!CopyMI->killsRegister(ImpLi.reg)) 00986 return false; 00987 // Make sure this is the only use. 00988 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(ImpLi.reg), 00989 UE = mri_->use_end(); UI != UE;) { 00990 MachineInstr *UseMI = &*UI; 00991 ++UI; 00992 if (CopyMI == UseMI || JoinedCopies.count(UseMI)) 00993 continue; 00994 return false; 00995 } 00996 return true; 00997 } 00998 00999 01000 /// isWinToJoinVRWithSrcPhysReg - Return true if it's worth while to join a 01001 /// a virtual destination register with physical source register. 01002 bool 01003 SimpleRegisterCoalescing::isWinToJoinVRWithSrcPhysReg(MachineInstr *CopyMI, 01004 MachineBasicBlock *CopyMBB, 01005 LiveInterval &DstInt, 01006 LiveInterval &SrcInt) { 01007 // If the virtual register live interval is long but it has low use desity, 01008 // do not join them, instead mark the physical register as its allocation 01009 // preference. 01010 const TargetRegisterClass *RC = mri_->getRegClass(DstInt.reg); 01011 unsigned Threshold = allocatableRCRegs_[RC].count() * 2; 01012 unsigned Length = li_->getApproximateInstructionCount(DstInt); 01013 if (Length > Threshold && 01014 (((float)std::distance(mri_->use_begin(DstInt.reg), 01015 mri_->use_end()) / Length) < (1.0 / Threshold))) 01016 return false; 01017 01018 // If the virtual register live interval extends into a loop, turn down 01019 // aggressiveness. 01020 unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); 01021 const MachineLoop *L = loopInfo->getLoopFor(CopyMBB); 01022 if (!L) { 01023 // Let's see if the virtual register live interval extends into the loop. 01024 LiveInterval::iterator DLR = DstInt.FindLiveRangeContaining(CopyIdx); 01025 assert(DLR != DstInt.end() && "Live range not found!"); 01026 DLR = DstInt.FindLiveRangeContaining(DLR->end+1); 01027 if (DLR != DstInt.end()) { 01028 CopyMBB = li_->getMBBFromIndex(DLR->start); 01029 L = loopInfo->getLoopFor(CopyMBB); 01030 } 01031 } 01032 01033 if (!L || Length <= Threshold) 01034 return true; 01035 01036 unsigned UseIdx = li_->getUseIndex(CopyIdx); 01037 LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx); 01038 MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start); 01039 if (loopInfo->getLoopFor(SMBB) != L) { 01040 if (!loopInfo->isLoopHeader(CopyMBB)) 01041 return false; 01042 // If vr's live interval extends pass the loop header, do not join. 01043 for (MachineBasicBlock::succ_iterator SI = CopyMBB->succ_begin(), 01044 SE = CopyMBB->succ_end(); SI != SE; ++SI) { 01045 MachineBasicBlock *SuccMBB = *SI; 01046 if (SuccMBB == CopyMBB) 01047 continue; 01048 if (DstInt.overlaps(li_->getMBBStartIdx(SuccMBB), 01049 li_->getMBBEndIdx(SuccMBB)+1)) 01050 return false; 01051 } 01052 } 01053 return true; 01054 } 01055 01056 /// isWinToJoinVRWithDstPhysReg - Return true if it's worth while to join a 01057 /// copy from a virtual source register to a physical destination register. 01058 bool 01059 SimpleRegisterCoalescing::isWinToJoinVRWithDstPhysReg(MachineInstr *CopyMI, 01060 MachineBasicBlock *CopyMBB, 01061 LiveInterval &DstInt, 01062 LiveInterval &SrcInt) { 01063 // If the virtual register live interval is long but it has low use desity, 01064 // do not join them, instead mark the physical register as its allocation 01065 // preference. 01066 const TargetRegisterClass *RC = mri_->getRegClass(SrcInt.reg); 01067 unsigned Threshold = allocatableRCRegs_[RC].count() * 2; 01068 unsigned Length = li_->getApproximateInstructionCount(SrcInt); 01069 if (Length > Threshold && 01070 (((float)std::distance(mri_->use_begin(SrcInt.reg), 01071 mri_->use_end()) / Length) < (1.0 / Threshold))) 01072 return false; 01073 01074 if (SrcInt.empty()) 01075 // Must be implicit_def. 01076 return false; 01077 01078 // If the virtual register live interval is defined or cross a loop, turn 01079 // down aggressiveness. 01080 unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); 01081 unsigned UseIdx = li_->getUseIndex(CopyIdx); 01082 LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx); 01083 assert(SLR != SrcInt.end() && "Live range not found!"); 01084 SLR = SrcInt.FindLiveRangeContaining(SLR->start-1); 01085 if (SLR == SrcInt.end()) 01086 return true; 01087 MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start); 01088 const MachineLoop *L = loopInfo->getLoopFor(SMBB); 01089 01090 if (!L || Length <= Threshold) 01091 return true; 01092 01093 if (loopInfo->getLoopFor(CopyMBB) != L) { 01094 if (SMBB != L->getLoopLatch()) 01095 return false; 01096 // If vr's live interval is extended from before the loop latch, do not 01097 // join. 01098 for (MachineBasicBlock::pred_iterator PI = SMBB->pred_begin(), 01099 PE = SMBB->pred_end(); PI != PE; ++PI) { 01100 MachineBasicBlock *PredMBB = *PI; 01101 if (PredMBB == SMBB) 01102 continue; 01103 if (SrcInt.overlaps(li_->getMBBStartIdx(PredMBB), 01104 li_->getMBBEndIdx(PredMBB)+1)) 01105 return false; 01106 } 01107 } 01108 return true; 01109 } 01110 01111 /// isWinToJoinCrossClass - Return true if it's profitable to coalesce 01112 /// two virtual registers from different register classes. 01113 bool 01114 SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned LargeReg, 01115 unsigned SmallReg, 01116 unsigned Threshold) { 01117 // Then make sure the intervals are *short*. 01118 LiveInterval &LargeInt = li_->getInterval(LargeReg); 01119 LiveInterval &SmallInt = li_->getInterval(SmallReg); 01120 unsigned LargeSize = li_->getApproximateInstructionCount(LargeInt); 01121 unsigned SmallSize = li_->getApproximateInstructionCount(SmallInt); 01122 if (SmallSize > Threshold || LargeSize > Threshold) 01123 if ((float)std::distance(mri_->use_begin(SmallReg), 01124 mri_->use_end()) / SmallSize < 01125 (float)std::distance(mri_->use_begin(LargeReg), 01126 mri_->use_end()) / LargeSize) 01127 return false; 01128 return true; 01129 } 01130 01131 /// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual 01132 /// register with a physical register, check if any of the virtual register 01133 /// operand is a sub-register use or def. If so, make sure it won't result 01134 /// in an illegal extract_subreg or insert_subreg instruction. e.g. 01135 /// vr1024 = extract_subreg vr1025, 1 01136 /// ... 01137 /// vr1024 = mov8rr AH 01138 /// If vr1024 is coalesced with AH, the extract_subreg is now illegal since 01139 /// AH does not have a super-reg whose sub-register 1 is AH. 01140 bool 01141 SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI, 01142 unsigned VirtReg, 01143 unsigned PhysReg) { 01144 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(VirtReg), 01145 E = mri_->reg_end(); I != E; ++I) { 01146 MachineOperand &O = I.getOperand(); 01147 MachineInstr *MI = &*I; 01148 if (MI == CopyMI || JoinedCopies.count(MI)) 01149 continue; 01150 unsigned SubIdx = O.getSubReg(); 01151 if (SubIdx && !tri_->getSubReg(PhysReg, SubIdx)) 01152 return true; 01153 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 01154 SubIdx = MI->getOperand(2).getImm(); 01155 if (O.isUse() && !tri_->getSubReg(PhysReg, SubIdx)) 01156 return true; 01157 if (O.isDef()) { 01158 unsigned SrcReg = MI->getOperand(1).getReg(); 01159 const TargetRegisterClass *RC = 01160 TargetRegisterInfo::isPhysicalRegister(SrcReg) 01161 ? tri_->getPhysicalRegisterRegClass(SrcReg) 01162 : mri_->getRegClass(SrcReg); 01163 if (!tri_->getMatchingSuperReg(PhysReg, SubIdx, RC)) 01164 return true; 01165 } 01166 } 01167 if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 01168 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { 01169 SubIdx = MI->getOperand(3).getImm(); 01170 if (VirtReg == MI->getOperand(0).getReg()) { 01171 if (!tri_->getSubReg(PhysReg, SubIdx)) 01172 return true; 01173 } else { 01174 unsigned DstReg = MI->getOperand(0).getReg(); 01175 const TargetRegisterClass *RC = 01176 TargetRegisterInfo::isPhysicalRegister(DstReg) 01177 ? tri_->getPhysicalRegisterRegClass(DstReg) 01178 : mri_->getRegClass(DstReg); 01179 if (!tri_->getMatchingSuperReg(PhysReg, SubIdx, RC)) 01180 return true; 01181 } 01182 } 01183 } 01184 return false; 01185 } 01186 01187 01188 /// CanJoinExtractSubRegToPhysReg - Return true if it's possible to coalesce 01189 /// an extract_subreg where dst is a physical register, e.g. 01190 /// cl = EXTRACT_SUBREG reg1024, 1 01191 bool 01192 SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(unsigned DstReg, 01193 unsigned SrcReg, unsigned SubIdx, 01194 unsigned &RealDstReg) { 01195 const TargetRegisterClass *RC = mri_->getRegClass(SrcReg); 01196 RealDstReg = tri_->getMatchingSuperReg(DstReg, SubIdx, RC); 01197 assert(RealDstReg && "Invalid extract_subreg instruction!"); 01198 01199 // For this type of EXTRACT_SUBREG, conservatively 01200 // check if the live interval of the source register interfere with the 01201 // actual super physical register we are trying to coalesce with. 01202 LiveInterval &RHS = li_->getInterval(SrcReg); 01203 if (li_->hasInterval(RealDstReg) && 01204 RHS.overlaps(li_->getInterval(RealDstReg))) { 01205 DOUT << "Interfere with register "; 01206 DEBUG(li_->getInterval(RealDstReg).print(DOUT, tri_)); 01207 return false; // Not coalescable 01208 } 01209 for (const unsigned* SR = tri_->getSubRegisters(RealDstReg); *SR; ++SR) 01210 if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { 01211 DOUT << "Interfere with sub-register "; 01212 DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); 01213 return false; // Not coalescable 01214 } 01215 return true; 01216 } 01217 01218 /// CanJoinInsertSubRegToPhysReg - Return true if it's possible to coalesce 01219 /// an insert_subreg where src is a physical register, e.g. 01220 /// reg1024 = INSERT_SUBREG reg1024, c1, 0 01221 bool 01222 SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(unsigned DstReg, 01223 unsigned SrcReg, unsigned SubIdx, 01224 unsigned &RealSrcReg) { 01225 const TargetRegisterClass *RC = mri_->getRegClass(DstReg); 01226 RealSrcReg = tri_->getMatchingSuperReg(SrcReg, SubIdx, RC); 01227 assert(RealSrcReg && "Invalid extract_subreg instruction!"); 01228 01229 LiveInterval &RHS = li_->getInterval(DstReg); 01230 if (li_->hasInterval(RealSrcReg) && 01231 RHS.overlaps(li_->getInterval(RealSrcReg))) { 01232 DOUT << "Interfere with register "; 01233 DEBUG(li_->getInterval(RealSrcReg).print(DOUT, tri_)); 01234 return false; // Not coalescable 01235 } 01236 for (const unsigned* SR = tri_->getSubRegisters(RealSrcReg); *SR; ++SR) 01237 if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { 01238 DOUT << "Interfere with sub-register "; 01239 DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); 01240 return false; // Not coalescable 01241 } 01242 return true; 01243 } 01244 01245 /// getRegAllocPreference - Return register allocation preference register. 01246 /// 01247 static unsigned getRegAllocPreference(unsigned Reg, MachineFunction &MF, 01248 MachineRegisterInfo *MRI, 01249 const TargetRegisterInfo *TRI) { 01250 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 01251 return 0; 01252 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(Reg); 01253 return TRI->ResolveRegAllocHint(Hint.first, Hint.second, MF); 01254 } 01255 01256 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 01257 /// which are the src/dst of the copy instruction CopyMI. This returns true 01258 /// if the copy was successfully coalesced away. If it is not currently 01259 /// possible to coalesce this interval, but it may be possible if other 01260 /// things get coalesced, then it returns true by reference in 'Again'. 01261 bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { 01262 MachineInstr *CopyMI = TheCopy.MI; 01263 01264 Again = false; 01265 if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI)) 01266 return false; // Already done. 01267 01268 DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI; 01269 01270 unsigned SrcReg, DstReg, SrcSubIdx = 0, DstSubIdx = 0; 01271 bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG; 01272 bool isInsSubReg = CopyMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG; 01273 bool isSubRegToReg = CopyMI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG; 01274 unsigned SubIdx = 0; 01275 if (isExtSubReg) { 01276 DstReg = CopyMI->getOperand(0).getReg(); 01277 DstSubIdx = CopyMI->getOperand(0).getSubReg(); 01278 SrcReg = CopyMI->getOperand(1).getReg(); 01279 SrcSubIdx = CopyMI->getOperand(2).getImm(); 01280 } else if (isInsSubReg || isSubRegToReg) { 01281 DstReg = CopyMI->getOperand(0).getReg(); 01282 DstSubIdx = CopyMI->getOperand(3).getImm(); 01283 SrcReg = CopyMI->getOperand(2).getReg(); 01284 SrcSubIdx = CopyMI->getOperand(2).getSubReg(); 01285 if (SrcSubIdx && SrcSubIdx != DstSubIdx) { 01286 // r1025 = INSERT_SUBREG r1025, r1024<2>, 2 Then r1024 has already been 01287 // coalesced to a larger register so the subreg indices cancel out. 01288 DOUT << "\tSource of insert_subreg is already coalesced " 01289 << "to another register.\n"; 01290 return false; // Not coalescable. 01291 } 01292 } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)){ 01293 llvm_unreachable("Unrecognized copy instruction!"); 01294 } 01295 01296 // If they are already joined we continue. 01297 if (SrcReg == DstReg) { 01298 DOUT << "\tCopy already coalesced.\n"; 01299 return false; // Not coalescable. 01300 } 01301 01302 bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 01303 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 01304 01305 // If they are both physical registers, we cannot join them. 01306 if (SrcIsPhys && DstIsPhys) { 01307 DOUT << "\tCan not coalesce physregs.\n"; 01308 return false; // Not coalescable. 01309 } 01310 01311 // We only join virtual registers with allocatable physical registers. 01312 if (SrcIsPhys && !allocatableRegs_[SrcReg]) { 01313 DOUT << "\tSrc reg is unallocatable physreg.\n"; 01314 return false; // Not coalescable. 01315 } 01316 if (DstIsPhys && !allocatableRegs_[DstReg]) { 01317 DOUT << "\tDst reg is unallocatable physreg.\n"; 01318 return false; // Not coalescable. 01319 } 01320 01321 // Check that a physical source register is compatible with dst regclass 01322 if (SrcIsPhys) { 01323 unsigned SrcSubReg = SrcSubIdx ? 01324 tri_->getSubReg(SrcReg, SrcSubIdx) : SrcReg; 01325 const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg); 01326 const TargetRegisterClass *DstSubRC = DstRC; 01327 if (DstSubIdx) 01328 DstSubRC = DstRC->getSubRegisterRegClass(DstSubIdx); 01329 assert(DstSubRC && "Illegal subregister index"); 01330 if (!DstSubRC->contains(SrcSubReg)) { 01331 DEBUG(errs() << "\tIncompatible destination regclass: " 01332 << tri_->getName(SrcSubReg) << " not in " << DstSubRC->getName() 01333 << ".\n"); 01334 return false; // Not coalescable. 01335 } 01336 } 01337 01338 // Check that a physical dst register is compatible with source regclass 01339 if (DstIsPhys) { 01340 unsigned DstSubReg = DstSubIdx ? 01341 tri_->getSubReg(DstReg, DstSubIdx) : DstReg; 01342 const TargetRegisterClass *SrcRC = mri_->getRegClass(SrcReg); 01343 const TargetRegisterClass *SrcSubRC = SrcRC; 01344 if (SrcSubIdx) 01345 SrcSubRC = SrcRC->getSubRegisterRegClass(SrcSubIdx); 01346 assert(SrcSubRC && "Illegal subregister index"); 01347 if (!SrcSubRC->contains(DstReg)) { 01348 DEBUG(errs() << "\tIncompatible source regclass: " 01349 << tri_->getName(DstSubReg) << " not in " << SrcSubRC->getName() 01350 << ".\n"); 01351 (void)DstSubReg; 01352 return false; // Not coalescable. 01353 } 01354 } 01355 01356 // Should be non-null only when coalescing to a sub-register class. 01357 bool CrossRC = false; 01358 const TargetRegisterClass *SrcRC= SrcIsPhys ? 0 : mri_->getRegClass(SrcReg); 01359 const TargetRegisterClass *DstRC= DstIsPhys ? 0 : mri_->getRegClass(DstReg); 01360 const TargetRegisterClass *NewRC = NULL; 01361 MachineBasicBlock *CopyMBB = CopyMI->getParent(); 01362 unsigned RealDstReg = 0; 01363 unsigned RealSrcReg = 0; 01364 if (isExtSubReg || isInsSubReg || isSubRegToReg) { 01365 SubIdx = CopyMI->getOperand(isExtSubReg ? 2 : 3).getImm(); 01366 if (SrcIsPhys && isExtSubReg) { 01367 // r1024 = EXTRACT_SUBREG EAX, 0 then r1024 is really going to be 01368 // coalesced with AX. 01369 unsigned DstSubIdx = CopyMI->getOperand(0).getSubReg(); 01370 if (DstSubIdx) { 01371 // r1024<2> = EXTRACT_SUBREG EAX, 2. Then r1024 has already been 01372 // coalesced to a larger register so the subreg indices cancel out. 01373 if (DstSubIdx != SubIdx) { 01374 DOUT << "\t Sub-register indices mismatch.\n"; 01375 return false; // Not coalescable. 01376 } 01377 } else 01378 SrcReg = tri_->getSubReg(SrcReg, SubIdx); 01379 SubIdx = 0; 01380 } else if (DstIsPhys && (isInsSubReg || isSubRegToReg)) { 01381 // EAX = INSERT_SUBREG EAX, r1024, 0 01382 unsigned SrcSubIdx = CopyMI->getOperand(2).getSubReg(); 01383 if (SrcSubIdx) { 01384 // EAX = INSERT_SUBREG EAX, r1024<2>, 2 Then r1024 has already been 01385 // coalesced to a larger register so the subreg indices cancel out. 01386 if (SrcSubIdx != SubIdx) { 01387 DOUT << "\t Sub-register indices mismatch.\n"; 01388 return false; // Not coalescable. 01389 } 01390 } else 01391 DstReg = tri_->getSubReg(DstReg, SubIdx); 01392 SubIdx = 0; 01393 } else if ((DstIsPhys && isExtSubReg) || 01394 (SrcIsPhys && (isInsSubReg || isSubRegToReg))) { 01395 if (!isSubRegToReg && CopyMI->getOperand(1).getSubReg()) { 01396 DOUT << "\tSrc of extract_subreg already coalesced with reg" 01397 << " of a super-class.\n"; 01398 return false; // Not coalescable. 01399 } 01400 01401 if (isExtSubReg) { 01402 if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealDstReg)) 01403 return false; // Not coalescable 01404 } else { 01405 if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg)) 01406 return false; // Not coalescable 01407 } 01408 SubIdx = 0; 01409 } else { 01410 unsigned OldSubIdx = isExtSubReg ? CopyMI->getOperand(0).getSubReg() 01411 : CopyMI->getOperand(2).getSubReg(); 01412 if (OldSubIdx) { 01413 if (OldSubIdx == SubIdx && !differingRegisterClasses(SrcReg, DstReg)) 01414 // r1024<2> = EXTRACT_SUBREG r1025, 2. Then r1024 has already been 01415 // coalesced to a larger register so the subreg indices cancel out. 01416 // Also check if the other larger register is of the same register 01417 // class as the would be resulting register. 01418 SubIdx = 0; 01419 else { 01420 DOUT << "\t Sub-register indices mismatch.\n"; 01421 return false; // Not coalescable. 01422 } 01423 } 01424 if (SubIdx) { 01425 if (!DstIsPhys && !SrcIsPhys) { 01426 if (isInsSubReg || isSubRegToReg) { 01427 NewRC = tri_->getMatchingSuperRegClass(DstRC, SrcRC, SubIdx); 01428 } else // extract_subreg { 01429 NewRC = tri_->getMatchingSuperRegClass(SrcRC, DstRC, SubIdx); 01430 } 01431 if (!NewRC) { 01432 DOUT << "\t Conflicting sub-register indices.\n"; 01433 return false; // Not coalescable 01434 } 01435 01436 unsigned LargeReg = isExtSubReg ? SrcReg : DstReg; 01437 unsigned SmallReg = isExtSubReg ? DstReg : SrcReg; 01438 unsigned Limit= allocatableRCRegs_[mri_->getRegClass(SmallReg)].count(); 01439 if (!isWinToJoinCrossClass(LargeReg, SmallReg, Limit)) { 01440 Again = true; // May be possible to coalesce later. 01441 return false; 01442 } 01443 } 01444 } 01445 } else if (differingRegisterClasses(SrcReg, DstReg)) { 01446 if (DisableCrossClassJoin) 01447 return false; 01448 CrossRC = true; 01449 01450 // FIXME: What if the result of a EXTRACT_SUBREG is then coalesced 01451 // with another? If it's the resulting destination register, then 01452 // the subidx must be propagated to uses (but only those defined 01453 // by the EXTRACT_SUBREG). If it's being coalesced into another 01454 // register, it should be safe because register is assumed to have 01455 // the register class of the super-register. 01456 01457 // Process moves where one of the registers have a sub-register index. 01458 MachineOperand *DstMO = CopyMI->findRegisterDefOperand(DstReg); 01459 MachineOperand *SrcMO = CopyMI->findRegisterUseOperand(SrcReg); 01460 SubIdx = DstMO->getSubReg(); 01461 if (SubIdx) { 01462 if (SrcMO->getSubReg()) 01463 // FIXME: can we handle this? 01464 return false; 01465 // This is not an insert_subreg but it looks like one. 01466 // e.g. %reg1024:4 = MOV32rr %EAX 01467 isInsSubReg = true; 01468 if (SrcIsPhys) { 01469 if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg)) 01470 return false; // Not coalescable 01471 SubIdx = 0; 01472 } 01473 } else { 01474 SubIdx = SrcMO->getSubReg(); 01475 if (SubIdx) { 01476 // This is not a extract_subreg but it looks like one. 01477 // e.g. %cl = MOV16rr %reg1024:1 01478 isExtSubReg = true; 01479 if (DstIsPhys) { 01480 if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx,RealDstReg)) 01481 return false; // Not coalescable 01482 SubIdx = 0; 01483 } 01484 } 01485 } 01486 01487 unsigned LargeReg = SrcReg; 01488 unsigned SmallReg = DstReg; 01489 01490 // Now determine the register class of the joined register. 01491 if (isExtSubReg) { 01492 if (SubIdx && DstRC && DstRC->isASubClass()) { 01493 // This is a move to a sub-register class. However, the source is a 01494 // sub-register of a larger register class. We don't know what should 01495 // the register class be. FIXME. 01496 Again = true; 01497 return false; 01498 } 01499 if (!DstIsPhys && !SrcIsPhys) 01500 NewRC = SrcRC; 01501 } else if (!SrcIsPhys && !DstIsPhys) { 01502 NewRC = getCommonSubClass(SrcRC, DstRC); 01503 if (!NewRC) { 01504 DEBUG(errs() << "\tDisjoint regclasses: " 01505 << SrcRC->getName() << ", " 01506 << DstRC->getName() << ".\n"); 01507 return false; // Not coalescable. 01508 } 01509 if (DstRC->getSize() > SrcRC->getSize()) 01510 std::swap(LargeReg, SmallReg); 01511 } 01512 01513 // If we are joining two virtual registers and the resulting register 01514 // class is more restrictive (fewer register, smaller size). Check if it's 01515 // worth doing the merge. 01516 if (!SrcIsPhys && !DstIsPhys && 01517 (isExtSubReg || DstRC->isASubClass()) && 01518 !isWinToJoinCrossClass(LargeReg, SmallReg, 01519 allocatableRCRegs_[NewRC].count())) { 01520 DOUT << "\tSrc/Dest are different register classes.\n"; 01521 // Allow the coalescer to try again in case either side gets coalesced to 01522 // a physical register that's compatible with the other side. e.g. 01523 // r1024 = MOV32to32_ r1025 01524 // But later r1024 is assigned EAX then r1025 may be coalesced with EAX. 01525 Again = true; // May be possible to coalesce later. 01526 return false; 01527 } 01528 } 01529 01530 // Will it create illegal extract_subreg / insert_subreg? 01531 if (SrcIsPhys && HasIncompatibleSubRegDefUse(CopyMI, DstReg, SrcReg)) 01532 return false; 01533 if (DstIsPhys && HasIncompatibleSubRegDefUse(CopyMI, SrcReg, DstReg)) 01534 return false; 01535 01536 LiveInterval &SrcInt = li_->getInterval(SrcReg); 01537 LiveInterval &DstInt = li_->getInterval(DstReg); 01538 assert(SrcInt.reg == SrcReg && DstInt.reg == DstReg && 01539 "Register mapping is horribly broken!"); 01540 01541 DOUT << "\t\tInspecting "; SrcInt.print(DOUT, tri_); 01542 DOUT << " and "; DstInt.print(DOUT, tri_); 01543 DOUT << ": "; 01544 01545 // Save a copy of the virtual register live interval. We'll manually 01546 // merge this into the "real" physical register live interval this is 01547 // coalesced with. 01548 LiveInterval *SavedLI = 0; 01549 if (RealDstReg) 01550 SavedLI = li_->dupInterval(&SrcInt); 01551 else if (RealSrcReg) 01552 SavedLI = li_->dupInterval(&DstInt); 01553 01554 // Check if it is necessary to propagate "isDead" property. 01555 if (!isExtSubReg && !isInsSubReg && !isSubRegToReg) { 01556 MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false); 01557 bool isDead = mopd->isDead(); 01558 01559 // We need to be careful about coalescing a source physical register with a 01560 // virtual register. Once the coalescing is done, it cannot be broken and 01561 // these are not spillable! If the destination interval uses are far away, 01562 // think twice about coalescing them! 01563 if (!isDead && (SrcIsPhys || DstIsPhys)) { 01564 // If the copy is in a loop, take care not to coalesce aggressively if the 01565 // src is coming in from outside the loop (or the dst is out of the loop). 01566 // If it's not in a loop, then determine whether to join them base purely 01567 // by the length of the interval. 01568 if (PhysJoinTweak) { 01569 if (SrcIsPhys) { 01570 if (!isWinToJoinVRWithSrcPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) { 01571 mri_->setRegAllocationHint(DstInt.reg, 0, SrcReg); 01572 ++numAborts; 01573 DOUT << "\tMay tie down a physical register, abort!\n"; 01574 Again = true; // May be possible to coalesce later. 01575 return false; 01576 } 01577 } else { 01578 if (!isWinToJoinVRWithDstPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) { 01579 mri_->setRegAllocationHint(SrcInt.reg, 0, DstReg); 01580 ++numAborts; 01581 DOUT << "\tMay tie down a physical register, abort!\n"; 01582 Again = true; // May be possible to coalesce later. 01583 return false; 01584 } 01585 } 01586 } else { 01587 // If the virtual register live interval is long but it has low use desity, 01588 // do not join them, instead mark the physical register as its allocation 01589 // preference. 01590 LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt; 01591 unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg; 01592 unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg; 01593 const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg); 01594 unsigned Threshold = allocatableRCRegs_[RC].count() * 2; 01595 if (TheCopy.isBackEdge) 01596 Threshold *= 2; // Favors back edge copies. 01597 01598 unsigned Length = li_->getApproximateInstructionCount(JoinVInt); 01599 float Ratio = 1.0 / Threshold; 01600 if (Length > Threshold && 01601 (((float)std::distance(mri_->use_begin(JoinVReg), 01602 mri_->use_end()) / Length) < Ratio)) { 01603 mri_->setRegAllocationHint(JoinVInt.reg, 0, JoinPReg); 01604 ++numAborts; 01605 DOUT << "\tMay tie down a physical register, abort!\n"; 01606 Again = true; // May be possible to coalesce later. 01607 return false; 01608 } 01609 } 01610 } 01611 } 01612 01613 // Okay, attempt to join these two intervals. On failure, this returns false. 01614 // Otherwise, if one of the intervals being joined is a physreg, this method 01615 // always canonicalizes DstInt to be it. The output "SrcInt" will not have 01616 // been modified, so we can use this information below to update aliases. 01617 bool Swapped = false; 01618 // If SrcInt is implicitly defined, it's safe to coalesce. 01619 bool isEmpty = SrcInt.empty(); 01620 if (isEmpty && !CanCoalesceWithImpDef(CopyMI, DstInt, SrcInt)) { 01621 // Only coalesce an empty interval (defined by implicit_def) with 01622 // another interval which has a valno defined by the CopyMI and the CopyMI 01623 // is a kill of the implicit def. 01624 DOUT << "Not profitable!\n"; 01625 return false; 01626 } 01627 01628 if (!isEmpty && !JoinIntervals(DstInt, SrcInt, Swapped)) { 01629 // Coalescing failed. 01630 01631 // If definition of source is defined by trivial computation, try 01632 // rematerializing it. 01633 if (!isExtSubReg && !isInsSubReg && !isSubRegToReg && 01634 ReMaterializeTrivialDef(SrcInt, DstReg, DstSubIdx, CopyMI)) 01635 return true; 01636 01637 // If we can eliminate the copy without merging the live ranges, do so now. 01638 if (!isExtSubReg && !isInsSubReg && !isSubRegToReg && 01639 (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI) || 01640 RemoveCopyByCommutingDef(SrcInt, DstInt, CopyMI))) { 01641 JoinedCopies.insert(CopyMI); 01642 return true; 01643 } 01644 01645 // Otherwise, we are unable to join the intervals. 01646 DOUT << "Interference!\n"; 01647 Again = true; // May be possible to coalesce later. 01648 return false; 01649 } 01650 01651 LiveInterval *ResSrcInt = &SrcInt; 01652 LiveInterval *ResDstInt = &DstInt; 01653 if (Swapped) { 01654 std::swap(SrcReg, DstReg); 01655 std::swap(ResSrcInt, ResDstInt); 01656 } 01657 assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 01658 "LiveInterval::join didn't work right!"); 01659 01660 // If we're about to merge live ranges into a physical register live interval, 01661 // we have to update any aliased register's live ranges to indicate that they 01662 // have clobbered values for this range. 01663 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 01664 // If this is a extract_subreg where dst is a physical register, e.g. 01665 // cl = EXTRACT_SUBREG reg1024, 1 01666 // then create and update the actual physical register allocated to RHS. 01667 if (RealDstReg || RealSrcReg) { 01668 LiveInterval &RealInt = 01669 li_->getOrCreateInterval(RealDstReg ? RealDstReg : RealSrcReg); 01670 for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(), 01671 E = SavedLI->vni_end(); I != E; ++I) { 01672 const VNInfo *ValNo = *I; 01673 VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->getCopy(), 01674 false, // updated at * 01675 li_->getVNInfoAllocator()); 01676 NewValNo->setFlags(ValNo->getFlags()); // * updated here. 01677 RealInt.addKills(NewValNo, ValNo->kills); 01678 RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo); 01679 } 01680 RealInt.weight += SavedLI->weight; 01681 DstReg = RealDstReg ? RealDstReg : RealSrcReg; 01682 } 01683 01684 // Update the liveintervals of sub-registers. 01685 for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS) 01686 li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt, 01687 li_->getVNInfoAllocator()); 01688 } 01689 01690 // If this is a EXTRACT_SUBREG, make sure the result of coalescing is the 01691 // larger super-register. 01692 if ((isExtSubReg || isInsSubReg || isSubRegToReg) && 01693 !SrcIsPhys && !DstIsPhys) { 01694 if ((isExtSubReg && !Swapped) || 01695 ((isInsSubReg || isSubRegToReg) && Swapped)) { 01696 ResSrcInt->Copy(*ResDstInt, mri_, li_->getVNInfoAllocator()); 01697 std::swap(SrcReg, DstReg); 01698 std::swap(ResSrcInt, ResDstInt); 01699 } 01700 } 01701 01702 // Coalescing to a virtual register that is of a sub-register class of the 01703 // other. Make sure the resulting register is set to the right register class. 01704 if (CrossRC) 01705 ++numCrossRCs; 01706 01707 // This may happen even if it's cross-rc coalescing. e.g. 01708 // %reg1026<def> = SUBREG_TO_REG 0, %reg1037<kill>, 4 01709 // reg1026 -> GR64, reg1037 -> GR32_ABCD. The resulting register will have to 01710 // be allocate a register from GR64_ABCD. 01711 if (NewRC) 01712 mri_->setRegClass(DstReg, NewRC); 01713 01714 if (NewHeuristic) { 01715 // Add all copies that define val# in the source interval into the queue. 01716 for (LiveInterval::const_vni_iterator i = ResSrcInt->vni_begin(), 01717 e = ResSrcInt->vni_end(); i != e; ++i) { 01718 const VNInfo *vni = *i; 01719 // FIXME: Do isPHIDef and isDefAccurate both need to be tested? 01720 if (!vni->def || vni->isUnused() || vni->isPHIDef() || !vni->isDefAccurate()) 01721 continue; 01722 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); 01723 unsigned NewSrcReg, NewDstReg, NewSrcSubIdx, NewDstSubIdx; 01724 if (CopyMI && 01725 JoinedCopies.count(CopyMI) == 0 && 01726 tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg, 01727 NewSrcSubIdx, NewDstSubIdx)) { 01728 unsigned LoopDepth = loopInfo->getLoopDepth(CopyMBB); 01729 JoinQueue->push(CopyRec(CopyMI, LoopDepth, 01730 isBackEdgeCopy(CopyMI, DstReg))); 01731 } 01732 } 01733 } 01734 01735 // Remember to delete the copy instruction. 01736 JoinedCopies.insert(CopyMI); 01737 01738 // Some live range has been lengthened due to colaescing, eliminate the 01739 // unnecessary kills. 01740 RemoveUnnecessaryKills(SrcReg, *ResDstInt); 01741 if (TargetRegisterInfo::isVirtualRegister(DstReg)) 01742 RemoveUnnecessaryKills(DstReg, *ResDstInt); 01743 01744 UpdateRegDefsUses(SrcReg, DstReg, SubIdx); 01745 01746 // SrcReg is guarateed to be the register whose live interval that is 01747 // being merged. 01748 li_->removeInterval(SrcReg); 01749 01750 // Update regalloc hint. 01751 tri_->UpdateRegAllocHint(SrcReg, DstReg, *mf_); 01752 01753 // Manually deleted the live interval copy. 01754 if (SavedLI) { 01755 SavedLI->clear(); 01756 delete SavedLI; 01757 } 01758 01759 // If resulting interval has a preference that no longer fits because of subreg 01760 // coalescing, just clear the preference. 01761 unsigned Preference = getRegAllocPreference(ResDstInt->reg, *mf_, mri_, tri_); 01762 if (Preference && (isExtSubReg || isInsSubReg || isSubRegToReg) && 01763 TargetRegisterInfo::isVirtualRegister(ResDstInt->reg)) { 01764 const TargetRegisterClass *RC = mri_->getRegClass(ResDstInt->reg); 01765 if (!RC->contains(Preference)) 01766 mri_->setRegAllocationHint(ResDstInt->reg, 0, 0); 01767 } 01768 01769 DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, tri_); 01770 DOUT << "\n"; 01771 01772 ++numJoins; 01773 return true; 01774 } 01775 01776 /// ComputeUltimateVN - Assuming we are going to join two live intervals, 01777 /// compute what the resultant value numbers for each value in the input two 01778 /// ranges will be. This is complicated by copies between the two which can 01779 /// and will commonly cause multiple value numbers to be merged into one. 01780 /// 01781 /// VN is the value number that we're trying to resolve. InstDefiningValue 01782 /// keeps track of the new InstDefiningValue assignment for the result 01783 /// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 01784 /// whether a value in this or other is a copy from the opposite set. 01785 /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 01786 /// already been assigned. 01787 /// 01788 /// ThisFromOther[x] - If x is defined as a copy from the other interval, this 01789 /// contains the value number the copy is from. 01790 /// 01791 static unsigned ComputeUltimateVN(VNInfo *VNI, 01792 SmallVector<VNInfo*, 16> &NewVNInfo, 01793 DenseMap<VNInfo*, VNInfo*> &ThisFromOther, 01794 DenseMap<VNInfo*, VNInfo*> &OtherFromThis, 01795 SmallVector<int, 16> &ThisValNoAssignments, 01796 SmallVector<int, 16> &OtherValNoAssignments) { 01797 unsigned VN = VNI->id; 01798 01799 // If the VN has already been computed, just return it. 01800 if (ThisValNoAssignments[VN] >= 0) 01801 return ThisValNoAssignments[VN]; 01802 // assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?"); 01803 01804 // If this val is not a copy from the other val, then it must be a new value 01805 // number in the destination. 01806 DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); 01807 if (I == ThisFromOther.end()) { 01808 NewVNInfo.push_back(VNI); 01809 return ThisValNoAssignments[VN] = NewVNInfo.size()-1; 01810 } 01811 VNInfo *OtherValNo = I->second; 01812 01813 // Otherwise, this *is* a copy from the RHS. If the other side has already 01814 // been computed, return it. 01815 if (OtherValNoAssignments[OtherValNo->id] >= 0) 01816 return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; 01817 01818 // Mark this value number as currently being computed, then ask what the 01819 // ultimate value # of the other value is. 01820 ThisValNoAssignments[VN] = -2; 01821 unsigned UltimateVN = 01822 ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, 01823 OtherValNoAssignments, ThisValNoAssignments); 01824 return ThisValNoAssignments[VN] = UltimateVN; 01825 } 01826 01827 static bool InVector(VNInfo *Val, const SmallVector<VNInfo*, 8> &V) { 01828 return std::find(V.begin(), V.end(), Val) != V.end(); 01829 } 01830 01831 /// RangeIsDefinedByCopyFromReg - Return true if the specified live range of 01832 /// the specified live interval is defined by a copy from the specified 01833 /// register. 01834 bool SimpleRegisterCoalescing::RangeIsDefinedByCopyFromReg(LiveInterval &li, 01835 LiveRange *LR, 01836 unsigned Reg) { 01837 unsigned SrcReg = li_->getVNInfoSourceReg(LR->valno); 01838 if (SrcReg == Reg) 01839 return true; 01840 // FIXME: Do isPHIDef and isDefAccurate both need to be tested? 01841 if ((LR->valno->isPHIDef() || !LR->valno->isDefAccurate()) && 01842 TargetRegisterInfo::isPhysicalRegister(li.reg) && 01843 *tri_->getSuperRegisters(li.reg)) { 01844 // It's a sub-register live interval, we may not have precise information. 01845 // Re-compute it. 01846 MachineInstr *DefMI = li_->getInstructionFromIndex(LR->start); 01847 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 01848 if (DefMI && 01849 tii_->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && 01850 DstReg == li.reg && SrcReg == Reg) { 01851 // Cache computed info. 01852 LR->valno->def = LR->start; 01853 LR->valno->setCopy(DefMI); 01854 return true; 01855 } 01856 } 01857 return false; 01858 } 01859 01860 /// SimpleJoin - Attempt to joint the specified interval into this one. The 01861 /// caller of this method must guarantee that the RHS only contains a single 01862 /// value number and that the RHS is not defined by a copy from this 01863 /// interval. This returns false if the intervals are not joinable, or it 01864 /// joins them and returns true. 01865 bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){ 01866 assert(RHS.containsOneValue()); 01867 01868 // Some number (potentially more than one) value numbers in the current 01869 // interval may be defined as copies from the RHS. Scan the overlapping 01870 // portions of the LHS and RHS, keeping track of this and looking for 01871 // overlapping live ranges that are NOT defined as copies. If these exist, we 01872 // cannot coalesce. 01873 01874 LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end(); 01875 LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end(); 01876 01877 if (LHSIt->start < RHSIt->start) { 01878 LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start); 01879 if (LHSIt != LHS.begin()) --LHSIt; 01880 } else if (RHSIt->start < LHSIt->start) { 01881 RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start); 01882 if (RHSIt != RHS.begin()) --RHSIt; 01883 } 01884 01885 SmallVector<VNInfo*, 8> EliminatedLHSVals; 01886 01887 while (1) { 01888 // Determine if these live intervals overlap. 01889 bool Overlaps = false; 01890 if (LHSIt->start <= RHSIt->start) 01891 Overlaps = LHSIt->end > RHSIt->start; 01892 else 01893 Overlaps = RHSIt->end > LHSIt->start; 01894 01895 // If the live intervals overlap, there are two interesting cases: if the 01896 // LHS interval is defined by a copy from the RHS, it's ok and we record 01897 // that the LHS value # is the same as the RHS. If it's not, then we cannot 01898 // coalesce these live ranges and we bail out. 01899 if (Overlaps) { 01900 // If we haven't already recorded that this value # is safe, check it. 01901 if (!InVector(LHSIt->valno, EliminatedLHSVals)) { 01902 // Copy from the RHS? 01903 if (!RangeIsDefinedByCopyFromReg(LHS, LHSIt, RHS.reg)) 01904 return false; // Nope, bail out. 01905 01906 if (LHSIt->contains(RHSIt->valno->def)) 01907 // Here is an interesting situation: 01908 // BB1: 01909 // vr1025 = copy vr1024 01910 // .. 01911 // BB2: 01912 // vr1024 = op 01913 // = vr1025 01914 // Even though vr1025 is copied from vr1024, it's not safe to 01915 // coalesce them since the live range of vr1025 intersects the 01916 // def of vr1024. This happens because vr1025 is assigned the 01917 // value of the previous iteration of vr1024. 01918 return false; 01919 EliminatedLHSVals.push_back(LHSIt->valno); 01920 } 01921 01922 // We know this entire LHS live range is okay, so skip it now. 01923 if (++LHSIt == LHSEnd) break; 01924 continue; 01925 } 01926 01927 if (LHSIt->end < RHSIt->end) { 01928 if (++LHSIt == LHSEnd) break; 01929 } else { 01930 // One interesting case to check here. It's possible that we have 01931 // something like "X3 = Y" which defines a new value number in the LHS, 01932 // and is the last use of this liverange of the RHS. In this case, we 01933 // want to notice this copy (so that it gets coalesced away) even though 01934 // the live ranges don't actually overlap. 01935 if (LHSIt->start == RHSIt->end) { 01936 if (InVector(LHSIt->valno, EliminatedLHSVals)) { 01937 // We already know that this value number is going to be merged in 01938 // if coalescing succeeds. Just skip the liverange. 01939 if (++LHSIt == LHSEnd) break; 01940 } else { 01941 // Otherwise, if this is a copy from the RHS, mark it as being merged 01942 // in. 01943 if (RangeIsDefinedByCopyFromReg(LHS, LHSIt, RHS.reg)) { 01944 if (LHSIt->contains(RHSIt->valno->def)) 01945 // Here is an interesting situation: 01946 // BB1: 01947 // vr1025 = copy vr1024 01948 // .. 01949 // BB2: 01950 // vr1024 = op 01951 // = vr1025 01952 // Even though vr1025 is copied from vr1024, it's not safe to 01953 // coalesced them since live range of vr1025 intersects the 01954 // def of vr1024. This happens because vr1025 is assigned the 01955 // value of the previous iteration of vr1024. 01956 return false; 01957 EliminatedLHSVals.push_back(LHSIt->valno); 01958 01959 // We know this entire LHS live range is okay, so skip it now. 01960 if (++LHSIt == LHSEnd) break; 01961 } 01962 } 01963 } 01964 01965 if (++RHSIt == RHSEnd) break; 01966 } 01967 } 01968 01969 // If we got here, we know that the coalescing will be successful and that 01970 // the value numbers in EliminatedLHSVals will all be merged together. Since 01971 // the most common case is that EliminatedLHSVals has a single number, we 01972 // optimize for it: if there is more than one value, we merge them all into 01973 // the lowest numbered one, then handle the interval as if we were merging 01974 // with one value number. 01975 VNInfo *LHSValNo = NULL; 01976 if (EliminatedLHSVals.size() > 1) { 01977 // Loop through all the equal value numbers merging them into the smallest 01978 // one. 01979 VNInfo *Smallest = EliminatedLHSVals[0]; 01980 for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) { 01981 if (EliminatedLHSVals[i]->id < Smallest->id) { 01982 // Merge the current notion of the smallest into the smaller one. 01983 LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]); 01984 Smallest = EliminatedLHSVals[i]; 01985 } else { 01986 // Merge into the smallest. 01987 LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest); 01988 } 01989 } 01990 LHSValNo = Smallest; 01991 } else if (EliminatedLHSVals.empty()) { 01992 if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) && 01993 *tri_->getSuperRegisters(LHS.reg)) 01994 // Imprecise sub-register information. Can't handle it. 01995 return false; 01996 llvm_unreachable("No copies from the RHS?"); 01997 } else { 01998 LHSValNo = EliminatedLHSVals[0]; 01999 } 02000 02001 // Okay, now that there is a single LHS value number that we're merging the 02002 // RHS into, update the value number info for the LHS to indicate that the 02003 // value number is defined where the RHS value number was. 02004 const VNInfo *VNI = RHS.getValNumInfo(0); 02005 LHSValNo->def = VNI->def; 02006 LHSValNo->setCopy(VNI->getCopy()); 02007 02008 // Okay, the final step is to loop over the RHS live intervals, adding them to 02009 // the LHS. 02010 if (VNI->hasPHIKill()) 02011 LHSValNo->setHasPHIKill(true); 02012 LHS.addKills(LHSValNo, VNI->kills); 02013 LHS.MergeRangesInAsValue(RHS, LHSValNo); 02014 02015 LHS.ComputeJoinedWeight(RHS); 02016 02017 // Update regalloc hint if both are virtual registers. 02018 if (TargetRegisterInfo::isVirtualRegister(LHS.reg) && 02019 TargetRegisterInfo::isVirtualRegister(RHS.reg)) { 02020 std::pair<unsigned, unsigned> RHSPref = mri_->getRegAllocationHint(RHS.reg); 02021 std::pair<unsigned, unsigned> LHSPref = mri_->getRegAllocationHint(LHS.reg); 02022 if (RHSPref != LHSPref) 02023 mri_->setRegAllocationHint(LHS.reg, RHSPref.first, RHSPref.second); 02024 } 02025 02026 // Update the liveintervals of sub-registers. 02027 if (TargetRegisterInfo::isPhysicalRegister(LHS.reg)) 02028 for (const unsigned *AS = tri_->getSubRegisters(LHS.reg); *AS; ++AS) 02029 li_->getOrCreateInterval(*AS).MergeInClobberRanges(LHS, 02030 li_->getVNInfoAllocator()); 02031 02032 return true; 02033 } 02034 02035 /// JoinIntervals - Attempt to join these two intervals. On failure, this 02036 /// returns false. Otherwise, if one of the intervals being joined is a 02037 /// physreg, this method always canonicalizes LHS to be it. The output 02038 /// "RHS" will not have been modified, so we can use this information 02039 /// below to update aliases. 02040 bool 02041 SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, 02042 bool &Swapped) { 02043 // Compute the final value assignment, assuming that the live ranges can be 02044 // coalesced. 02045 SmallVector<int, 16> LHSValNoAssignments; 02046 SmallVector<int, 16> RHSValNoAssignments; 02047 DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; 02048 DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; 02049 SmallVector<VNInfo*, 16> NewVNInfo; 02050 02051 // If a live interval is a physical register, conservatively check if any 02052 // of its sub-registers is overlapping the live interval of the virtual 02053 // register. If so, do not coalesce. 02054 if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) && 02055 *tri_->getSubRegisters(LHS.reg)) { 02056 // If it's coalescing a virtual register to a physical register, estimate 02057 // its live interval length. This is the *cost* of scanning an entire live 02058 // interval. If the cost is low, we'll do an exhaustive check instead. 02059 02060 // If this is something like this: 02061 // BB1: 02062 // v1024 = op 02063 // ... 02064 // BB2: 02065 // ... 02066 // RAX = v1024 02067 // 02068 // That is, the live interval of v1024 crosses a bb. Then we can't rely on 02069 // less conservative check. It's possible a sub-register is defined before 02070 // v1024 (or live in) and live out of BB1. 02071 if (RHS.containsOneValue() && 02072 li_->intervalIsInOneMBB(RHS) && 02073 li_->getApproximateInstructionCount(RHS) <= 10) { 02074 // Perform a more exhaustive check for some common cases. 02075 if (li_->conflictsWithPhysRegRef(RHS, LHS.reg, true, JoinedCopies)) 02076 return false; 02077 } else { 02078 for (const unsigned* SR = tri_->getSubRegisters(LHS.reg); *SR; ++SR) 02079 if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { 02080 DOUT << "Interfere with sub-register "; 02081 DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); 02082 return false; 02083 } 02084 } 02085 } else if (TargetRegisterInfo::isPhysicalRegister(RHS.reg) && 02086 *tri_->getSubRegisters(RHS.reg)) { 02087 if (LHS.containsOneValue() && 02088 li_->getApproximateInstructionCount(LHS) <= 10) { 02089 // Perform a more exhaustive check for some common cases. 02090 if (li_->conflictsWithPhysRegRef(LHS, RHS.reg, false, JoinedCopies)) 02091 return false; 02092 } else { 02093 for (const unsigned* SR = tri_->getSubRegisters(RHS.reg); *SR; ++SR) 02094 if (li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) { 02095 DOUT << "Interfere with sub-register "; 02096 DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); 02097 return false; 02098 } 02099 } 02100 } 02101 02102 // Compute ultimate value numbers for the LHS and RHS values. 02103 if (RHS.containsOneValue()) { 02104 // Copies from a liveinterval with a single value are simple to handle and 02105 // very common, handle the special case here. This is important, because 02106 // often RHS is small and LHS is large (e.g. a physreg). 02107 02108 // Find out if the RHS is defined as a copy from some value in the LHS. 02109 int RHSVal0DefinedFromLHS = -1; 02110 int RHSValID = -1; 02111 VNInfo *RHSValNoInfo = NULL; 02112 VNInfo *RHSValNoInfo0 = RHS.getValNumInfo(0); 02113 unsigned RHSSrcReg = li_->getVNInfoSourceReg(RHSValNoInfo0); 02114 if (RHSSrcReg == 0 || RHSSrcReg != LHS.reg) { 02115 // If RHS is not defined as a copy from the LHS, we can use simpler and 02116 // faster checks to see if the live ranges are coalescable. This joiner 02117 // can't swap the LHS/RHS intervals though. 02118 if (!TargetRegisterInfo::isPhysicalRegister(RHS.reg)) { 02119 return SimpleJoin(LHS, RHS); 02120 } else { 02121 RHSValNoInfo = RHSValNoInfo0; 02122 } 02123 } else { 02124 // It was defined as a copy from the LHS, find out what value # it is. 02125 RHSValNoInfo = LHS.getLiveRangeContaining(RHSValNoInfo0->def-1)->valno; 02126 RHSValID = RHSValNoInfo->id; 02127 RHSVal0DefinedFromLHS = RHSValID; 02128 } 02129 02130 LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 02131 RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 02132 NewVNInfo.resize(LHS.getNumValNums(), NULL); 02133 02134 // Okay, *all* of the values in LHS that are defined as a copy from RHS 02135 // should now get updated. 02136 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 02137 i != e; ++i) { 02138 VNInfo *VNI = *i; 02139 unsigned VN = VNI->id; 02140 if (unsigned LHSSrcReg = li_->getVNInfoSourceReg(VNI)) { 02141 if (LHSSrcReg != RHS.reg) { 02142 // If this is not a copy from the RHS, its value number will be 02143 // unmodified by the coalescing. 02144 NewVNInfo[VN] = VNI; 02145 LHSValNoAssignments[VN] = VN; 02146 } else if (RHSValID == -1) { 02147 // Otherwise, it is a copy from the RHS, and we don't already have a 02148 // value# for it. Keep the current value number, but remember it. 02149 LHSValNoAssignments[VN] = RHSValID = VN; 02150 NewVNInfo[VN] = RHSValNoInfo; 02151 LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0; 02152 } else { 02153 // Otherwise, use the specified value #. 02154 LHSValNoAssignments[VN] = RHSValID; 02155 if (VN == (unsigned)RHSValID) { // Else this val# is dead. 02156 NewVNInfo[VN] = RHSValNoInfo; 02157 LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0; 02158 } 02159 } 02160 } else { 02161 NewVNInfo[VN] = VNI; 02162 LHSValNoAssignments[VN] = VN; 02163 } 02164 } 02165 02166 assert(RHSValID != -1 && "Didn't find value #?"); 02167 RHSValNoAssignments[0] = RHSValID; 02168 if (RHSVal0DefinedFromLHS != -1) { 02169 // This path doesn't go through ComputeUltimateVN so just set 02170 // it to anything. 02171 RHSValsDefinedFromLHS[RHSValNoInfo0] = (VNInfo*)1; 02172 } 02173 } else { 02174 // Loop over the value numbers of the LHS, seeing if any are defined from 02175 // the RHS. 02176 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 02177 i != e; ++i) { 02178 VNInfo *VNI = *i; 02179 if (VNI->isUnused() || VNI->getCopy() == 0) // Src not defined by a copy? 02180 continue; 02181 02182 // DstReg is known to be a register in the LHS interval. If the src is 02183 // from the RHS interval, we can use its value #. 02184 if (li_->getVNInfoSourceReg(VNI) != RHS.reg) 02185 continue; 02186 02187 // Figure out the value # from the RHS. 02188 LHSValsDefinedFromRHS[VNI]=RHS.getLiveRangeContaining(VNI->def-1)->valno; 02189 } 02190 02191 // Loop over the value numbers of the RHS, seeing if any are defined from 02192 // the LHS. 02193 for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 02194 i != e; ++i) { 02195 VNInfo *VNI = *i; 02196 if (VNI->isUnused() || VNI->getCopy() == 0) // Src not defined by a copy? 02197 continue; 02198 02199 // DstReg is known to be a register in the RHS interval. If the src is 02200 // from the LHS interval, we can use its value #. 02201 if (li_->getVNInfoSourceReg(VNI) != LHS.reg) 02202 continue; 02203 02204 // Figure out the value # from the LHS. 02205 RHSValsDefinedFromLHS[VNI]=LHS.getLiveRangeContaining(VNI->def-1)->valno; 02206 } 02207 02208 LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 02209 RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 02210 NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 02211 02212 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 02213 i != e; ++i) { 02214 VNInfo *VNI = *i; 02215 unsigned VN = VNI->id; 02216 if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 02217 continue; 02218 ComputeUltimateVN(VNI, NewVNInfo, 02219 LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 02220 LHSValNoAssignments, RHSValNoAssignments); 02221 } 02222 for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 02223 i != e; ++i) { 02224 VNInfo *VNI = *i; 02225 unsigned VN = VNI->id; 02226 if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 02227 continue; 02228 // If this value number isn't a copy from the LHS, it's a new number. 02229 if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { 02230 NewVNInfo.push_back(VNI); 02231 RHSValNoAssignments[VN] = NewVNInfo.size()-1; 02232 continue; 02233 } 02234 02235 ComputeUltimateVN(VNI, NewVNInfo, 02236 RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 02237 RHSValNoAssignments, LHSValNoAssignments); 02238 } 02239 } 02240 02241 // Armed with the mappings of LHS/RHS values to ultimate values, walk the 02242 // interval lists to see if these intervals are coalescable. 02243 LiveInterval::const_iterator I = LHS.begin(); 02244 LiveInterval::const_iterator IE = LHS.end(); 02245 LiveInterval::const_iterator J = RHS.begin(); 02246 LiveInterval::const_iterator JE = RHS.end(); 02247 02248 // Skip ahead until the first place of potential sharing. 02249 if (I->start < J->start) { 02250 I = std::upper_bound(I, IE, J->start); 02251 if (I != LHS.begin()) --I; 02252 } else if (J->start < I->start) { 02253 J = std::upper_bound(J, JE, I->start); 02254 if (J != RHS.begin()) --J; 02255 } 02256 02257 while (1) { 02258 // Determine if these two live ranges overlap. 02259 bool Overlaps; 02260 if (I->start < J->start) { 02261 Overlaps = I->end > J->start; 02262 } else { 02263 Overlaps = J->end > I->start; 02264 } 02265 02266 // If so, check value # info to determine if they are really different. 02267 if (Overlaps) { 02268 // If the live range overlap will map to the same value number in the 02269 // result liverange, we can still coalesce them. If not, we can't. 02270 if (LHSValNoAssignments[I->valno->id] != 02271 RHSValNoAssignments[J->valno->id]) 02272 return false; 02273 } 02274 02275 if (I->end < J->end) { 02276 ++I; 02277 if (I == IE) break; 02278 } else { 02279 ++J; 02280 if (J == JE) break; 02281 } 02282 } 02283 02284 // Update kill info. Some live ranges are extended due to copy coalescing. 02285 for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(), 02286 E = LHSValsDefinedFromRHS.end(); I != E; ++I) { 02287 VNInfo *VNI = I->first; 02288 unsigned LHSValID = LHSValNoAssignments[VNI->id]; 02289 LiveInterval::removeKill(NewVNInfo[LHSValID], VNI->def); 02290 if (VNI->hasPHIKill()) 02291 NewVNInfo[LHSValID]->setHasPHIKill(true); 02292 RHS.addKills(NewVNInfo[LHSValID], VNI->kills); 02293 } 02294 02295 // Update kill info. Some live ranges are extended due to copy coalescing. 02296 for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(), 02297 E = RHSValsDefinedFromLHS.end(); I != E; ++I) { 02298 VNInfo *VNI = I->first; 02299 unsigned RHSValID = RHSValNoAssignments[VNI->id]; 02300 LiveInterval::removeKill(NewVNInfo[RHSValID], VNI->def); 02301 if (VNI->hasPHIKill()) 02302 NewVNInfo[RHSValID]->setHasPHIKill(true); 02303 LHS.addKills(NewVNInfo[RHSValID], VNI->kills); 02304 } 02305 02306 // If we get here, we know that we can coalesce the live ranges. Ask the 02307 // intervals to coalesce themselves now. 02308 if ((RHS.ranges.size() > LHS.ranges.size() && 02309 TargetRegisterInfo::isVirtualRegister(LHS.reg)) || 02310 TargetRegisterInfo::isPhysicalRegister(RHS.reg)) { 02311 RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo, 02312 mri_); 02313 Swapped = true; 02314 } else { 02315 LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, 02316 mri_); 02317 Swapped = false; 02318 } 02319 return true; 02320 } 02321 02322 namespace { 02323 // DepthMBBCompare - Comparison predicate that sort first based on the loop 02324 // depth of the basic block (the unsigned), and then on the MBB number. 02325 struct DepthMBBCompare { 02326 typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 02327 bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 02328 if (LHS.first > RHS.first) return true; // Deeper loops first 02329 return LHS.first == RHS.first && 02330 LHS.second->getNumber() < RHS.second->getNumber(); 02331 } 02332 }; 02333 } 02334 02335 /// getRepIntervalSize - Returns the size of the interval that represents the 02336 /// specified register. 02337 template<class SF> 02338 unsigned JoinPriorityQueue<SF>::getRepIntervalSize(unsigned Reg) { 02339 return Rc->getRepIntervalSize(Reg); 02340 } 02341 02342 /// CopyRecSort::operator - Join priority queue sorting function. 02343 /// 02344 bool CopyRecSort::operator()(CopyRec left, CopyRec right) const { 02345 // Inner loops first. 02346 if (left.LoopDepth > right.LoopDepth) 02347 return false; 02348 else if (left.LoopDepth == right.LoopDepth) 02349 if (left.isBackEdge && !right.isBackEdge) 02350 return false; 02351 return true; 02352 } 02353 02354 void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB, 02355 std::vector<CopyRec> &TryAgain) { 02356 DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 02357 02358 std::vector<CopyRec> VirtCopies; 02359 std::vector<CopyRec> PhysCopies; 02360 std::vector<CopyRec> ImpDefCopies; 02361 unsigned LoopDepth = loopInfo->getLoopDepth(MBB); 02362 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 02363 MII != E;) { 02364 MachineInstr *Inst = MII++; 02365 02366 // If this isn't a copy nor a extract_subreg, we can't join intervals. 02367 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 02368 if (Inst->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 02369 DstReg = Inst->getOperand(0).getReg(); 02370 SrcReg = Inst->getOperand(1).getReg(); 02371 } else if (Inst->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 02372 Inst->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { 02373 DstReg = Inst->getOperand(0).getReg(); 02374 SrcReg = Inst->getOperand(2).getReg(); 02375 } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) 02376 continue; 02377 02378 bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 02379 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 02380 if (NewHeuristic) { 02381 JoinQueue->push(CopyRec(Inst, LoopDepth, isBackEdgeCopy(Inst, DstReg))); 02382 } else { 02383 if (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty()) 02384 ImpDefCopies.push_back(CopyRec(Inst, 0, false)); 02385 else if (SrcIsPhys || DstIsPhys) 02386 PhysCopies.push_back(CopyRec(Inst, 0, false)); 02387 else 02388 VirtCopies.push_back(CopyRec(Inst, 0, false)); 02389 } 02390 } 02391 02392 if (NewHeuristic) 02393 return; 02394 02395 // Try coalescing implicit copies first, followed by copies to / from 02396 // physical registers, then finally copies from virtual registers to 02397 // virtual registers. 02398 for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) { 02399 CopyRec &TheCopy = ImpDefCopies[i]; 02400 bool Again = false; 02401 if (!JoinCopy(TheCopy, Again)) 02402 if (Again) 02403 TryAgain.push_back(TheCopy); 02404 } 02405 for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) { 02406 CopyRec &TheCopy = PhysCopies[i]; 02407 bool Again = false; 02408 if (!JoinCopy(TheCopy, Again)) 02409 if (Again) 02410 TryAgain.push_back(TheCopy); 02411 } 02412 for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) { 02413 CopyRec &TheCopy = VirtCopies[i]; 02414 bool Again = false; 02415 if (!JoinCopy(TheCopy, Again)) 02416 if (Again) 02417 TryAgain.push_back(TheCopy); 02418 } 02419 } 02420 02421 void SimpleRegisterCoalescing::joinIntervals() { 02422 DOUT << "********** JOINING INTERVALS ***********\n"; 02423 02424 if (NewHeuristic) 02425 JoinQueue = new JoinPriorityQueue<CopyRecSort>(this); 02426 02427 std::vector<CopyRec> TryAgainList; 02428 if (loopInfo->empty()) { 02429 // If there are no loops in the function, join intervals in function order. 02430 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 02431 I != E; ++I) 02432 CopyCoalesceInMBB(I, TryAgainList); 02433 } else { 02434 // Otherwise, join intervals in inner loops before other intervals. 02435 // Unfortunately we can't just iterate over loop hierarchy here because 02436 // there may be more MBB's than BB's. Collect MBB's for sorting. 02437 02438 // Join intervals in the function prolog first. We want to join physical 02439 // registers with virtual registers before the intervals got too long. 02440 std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 02441 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){ 02442 MachineBasicBlock *MBB = I; 02443 MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I)); 02444 } 02445 02446 // Sort by loop depth. 02447 std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 02448 02449 // Finally, join intervals in loop nest order. 02450 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 02451 CopyCoalesceInMBB(MBBs[i].second, TryAgainList); 02452 } 02453 02454 // Joining intervals can allow other intervals to be joined. Iteratively join 02455 // until we make no progress. 02456 if (NewHeuristic) { 02457 SmallVector<CopyRec, 16> TryAgain; 02458 bool ProgressMade = true; 02459 while (ProgressMade) { 02460 ProgressMade = false; 02461 while (!JoinQueue->empty()) { 02462 CopyRec R = JoinQueue->pop(); 02463 bool Again = false; 02464 bool Success = JoinCopy(R, Again); 02465 if (Success) 02466 ProgressMade = true; 02467 else if (Again) 02468 TryAgain.push_back(R); 02469 } 02470 02471 if (ProgressMade) { 02472 while (!TryAgain.empty()) { 02473 JoinQueue->push(TryAgain.back()); 02474 TryAgain.pop_back(); 02475 } 02476 } 02477 } 02478 } else { 02479 bool ProgressMade = true; 02480 while (ProgressMade) { 02481 ProgressMade = false; 02482 02483 for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { 02484 CopyRec &TheCopy = TryAgainList[i]; 02485 if (TheCopy.MI) { 02486 bool Again = false; 02487 bool Success = JoinCopy(TheCopy, Again); 02488 if (Success || !Again) { 02489 TheCopy.MI = 0; // Mark this one as done. 02490 ProgressMade = true; 02491 } 02492 } 02493 } 02494 } 02495 } 02496 02497 if (NewHeuristic) 02498 delete JoinQueue; 02499 } 02500 02501 /// Return true if the two specified registers belong to different register 02502 /// classes. The registers may be either phys or virt regs. 02503 bool 02504 SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, 02505 unsigned RegB) const { 02506 // Get the register classes for the first reg. 02507 if (TargetRegisterInfo::isPhysicalRegister(RegA)) { 02508 assert(TargetRegisterInfo::isVirtualRegister(RegB) && 02509 "Shouldn't consider two physregs!"); 02510 return !mri_->getRegClass(RegB)->contains(RegA); 02511 } 02512 02513 // Compare against the regclass for the second reg. 02514 const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA); 02515 if (TargetRegisterInfo::isVirtualRegister(RegB)) { 02516 const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB); 02517 return RegClassA != RegClassB; 02518 } 02519 return !RegClassA->contains(RegB); 02520 } 02521 02522 /// lastRegisterUse - Returns the last use of the specific register between 02523 /// cycles Start and End or NULL if there are no uses. 02524 MachineOperand * 02525 SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, 02526 unsigned Reg, unsigned &UseIdx) const{ 02527 UseIdx = 0; 02528 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 02529 MachineOperand *LastUse = NULL; 02530 for (MachineRegisterInfo::use_iterator I = mri_->use_begin(Reg), 02531 E = mri_->use_end(); I != E; ++I) { 02532 MachineOperand &Use = I.getOperand(); 02533 MachineInstr *UseMI = Use.getParent(); 02534 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 02535 if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && 02536 SrcReg == DstReg) 02537 // Ignore identity copies. 02538 continue; 02539 unsigned Idx = li_->getInstructionIndex(UseMI); 02540 if (Idx >= Start && Idx < End && Idx >= UseIdx) { 02541 LastUse = &Use; 02542 UseIdx = li_->getUseIndex(Idx); 02543 } 02544 } 02545 return LastUse; 02546 } 02547 02548 int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM; 02549 int s = Start; 02550 while (e >= s) { 02551 // Skip deleted instructions 02552 MachineInstr *MI = li_->getInstructionFromIndex(e); 02553 while ((e - InstrSlots::NUM) >= s && !MI) { 02554 e -= InstrSlots::NUM; 02555 MI = li_->getInstructionFromIndex(e); 02556 } 02557 if (e < s || MI == NULL) 02558 return NULL; 02559 02560 // Ignore identity copies. 02561 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 02562 if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && 02563 SrcReg == DstReg)) 02564 for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) { 02565 MachineOperand &Use = MI->getOperand(i); 02566 if (Use.isReg() && Use.isUse() && Use.getReg() && 02567 tri_->regsOverlap(Use.getReg(), Reg)) { 02568 UseIdx = li_->getUseIndex(e); 02569 return &Use; 02570 } 02571 } 02572 02573 e -= InstrSlots::NUM; 02574 } 02575 02576 return NULL; 02577 } 02578 02579 02580 void SimpleRegisterCoalescing::printRegName(unsigned reg) const { 02581 if (TargetRegisterInfo::isPhysicalRegister(reg)) 02582 cerr << tri_->getName(reg); 02583 else 02584 cerr << "%reg" << reg; 02585 } 02586 02587 void SimpleRegisterCoalescing::releaseMemory() { 02588 JoinedCopies.clear(); 02589 ReMatCopies.clear(); 02590 ReMatDefs.clear(); 02591 } 02592 02593 static bool isZeroLengthInterval(LiveInterval *li) { 02594 for (LiveInterval::Ranges::const_iterator 02595 i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) 02596 if (i->end - i->start > LiveInterval::InstrSlots::NUM) 02597 return false; 02598 return true; 02599 } 02600 02601 02602 bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { 02603 mf_ = &fn; 02604 mri_ = &fn.getRegInfo(); 02605 tm_ = &fn.getTarget(); 02606 tri_ = tm_->getRegisterInfo(); 02607 tii_ = tm_->getInstrInfo(); 02608 li_ = &getAnalysis<LiveIntervals>(); 02609 loopInfo = &getAnalysis<MachineLoopInfo>(); 02610 02611 DEBUG(errs() << "********** SIMPLE REGISTER COALESCING **********\n" 02612 << "********** Function: " 02613 << ((Value*)mf_->getFunction())->getName() << '\n'); 02614 02615 allocatableRegs_ = tri_->getAllocatableSet(fn); 02616 for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(), 02617 E = tri_->regclass_end(); I != E; ++I) 02618 allocatableRCRegs_.insert(std::make_pair(*I, 02619 tri_->getAllocatableSet(fn, *I))); 02620 02621 // Join (coalesce) intervals if requested. 02622 if (EnableJoining) { 02623 joinIntervals(); 02624 DEBUG({ 02625 DOUT << "********** INTERVALS POST JOINING **********\n"; 02626 for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I){ 02627 I->second->print(DOUT, tri_); 02628 DOUT << "\n"; 02629 } 02630 }); 02631 } 02632 02633 // Perform a final pass over the instructions and compute spill weights 02634 // and remove identity moves. 02635 SmallVector<unsigned, 4> DeadDefs; 02636 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 02637 mbbi != mbbe; ++mbbi) { 02638 MachineBasicBlock* mbb = mbbi; 02639 unsigned loopDepth = loopInfo->getLoopDepth(mbb); 02640 02641 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 02642 mii != mie; ) { 02643 MachineInstr *MI = mii; 02644 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 02645 if (JoinedCopies.count(MI)) { 02646 // Delete all coalesced copies. 02647 if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) { 02648 assert((MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 02649 MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 02650 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) && 02651 "Unrecognized copy instruction"); 02652 DstReg = MI->getOperand(0).getReg(); 02653 } 02654 if (MI->registerDefIsDead(DstReg)) { 02655 LiveInterval &li = li_->getInterval(DstReg); 02656 if (!ShortenDeadCopySrcLiveRange(li, MI)) 02657 ShortenDeadCopyLiveRange(li, MI); 02658 } 02659 li_->RemoveMachineInstrFromMaps(MI); 02660 mii = mbbi->erase(mii); 02661 ++numPeep; 02662 continue; 02663 } 02664 02665 // Now check if this is a remat'ed def instruction which is now dead. 02666 if (ReMatDefs.count(MI)) { 02667 bool isDead = true; 02668 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 02669 const MachineOperand &MO = MI->getOperand(i); 02670 if (!MO.isReg()) 02671 continue; 02672 unsigned Reg = MO.getReg(); 02673 if (!Reg) 02674 continue; 02675 if (TargetRegisterInfo::isVirtualRegister(Reg)) 02676 DeadDefs.push_back(Reg); 02677 if (MO.isDead()) 02678 continue; 02679 if (TargetRegisterInfo::isPhysicalRegister(Reg) || 02680 !mri_->use_empty(Reg)) { 02681 isDead = false; 02682 break; 02683 } 02684 } 02685 if (isDead) { 02686 while (!DeadDefs.empty()) { 02687 unsigned DeadDef = DeadDefs.back(); 02688 DeadDefs.pop_back(); 02689 RemoveDeadDef(li_->getInterval(DeadDef), MI); 02690 } 02691 li_->RemoveMachineInstrFromMaps(mii); 02692 mii = mbbi->erase(mii); 02693 continue; 02694 } else 02695 DeadDefs.clear(); 02696 } 02697 02698 // If the move will be an identity move delete it 02699 bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx); 02700 if (isMove && SrcReg == DstReg) { 02701 if (li_->hasInterval(SrcReg)) { 02702 LiveInterval &RegInt = li_->getInterval(SrcReg); 02703 // If def of this move instruction is dead, remove its live range 02704 // from the dstination register's live interval. 02705 if (MI->registerDefIsDead(DstReg)) { 02706 if (!ShortenDeadCopySrcLiveRange(RegInt, MI)) 02707 ShortenDeadCopyLiveRange(RegInt, MI); 02708 } 02709 } 02710 li_->RemoveMachineInstrFromMaps(MI); 02711 mii = mbbi->erase(mii); 02712 ++numPeep; 02713 } else { 02714 SmallSet<unsigned, 4> UniqueUses; 02715 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 02716 const MachineOperand &mop = MI->getOperand(i); 02717 if (mop.isReg() && mop.getReg() && 02718 TargetRegisterInfo::isVirtualRegister(mop.getReg())) { 02719 unsigned reg = mop.getReg(); 02720 // Multiple uses of reg by the same instruction. It should not 02721 // contribute to spill weight again. 02722 if (UniqueUses.count(reg) != 0) 02723 continue; 02724 LiveInterval &RegInt = li_->getInterval(reg); 02725 RegInt.weight += 02726 li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth); 02727 UniqueUses.insert(reg); 02728 } 02729 } 02730 ++mii; 02731 } 02732 } 02733 } 02734 02735 for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) { 02736 LiveInterval &LI = *I->second; 02737 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { 02738 // If the live interval length is essentially zero, i.e. in every live 02739 // range the use follows def immediately, it doesn't make sense to spill 02740 // it and hope it will be easier to allocate for this li. 02741 if (isZeroLengthInterval(&LI)) 02742 LI.weight = HUGE_VALF; 02743 else { 02744 bool isLoad = false; 02745 SmallVector<LiveInterval*, 4> SpillIs; 02746 if (li_->isReMaterializable(LI, SpillIs, isLoad)) { 02747 // If all of the definitions of the interval are re-materializable, 02748 // it is a preferred candidate for spilling. If non of the defs are 02749 // loads, then it's potentially very cheap to re-materialize. 02750 // FIXME: this gets much more complicated once we support non-trivial 02751 // re-materialization. 02752 if (isLoad) 02753 LI.weight *= 0.9F; 02754 else 02755 LI.weight *= 0.5F; 02756 } 02757 } 02758 02759 // Slightly prefer live interval that has been assigned a preferred reg. 02760 std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(LI.reg); 02761 if (Hint.first || Hint.second) 02762 LI.weight *= 1.01F; 02763 02764 // Divide the weight of the interval by its size. This encourages 02765 // spilling of intervals that are large and have few uses, and 02766 // discourages spilling of small intervals with many uses. 02767 LI.weight /= li_->getApproximateInstructionCount(LI) * InstrSlots::NUM; 02768 } 02769 } 02770 02771 DEBUG(dump()); 02772 return true; 02773 } 02774 02775 /// print - Implement the dump method. 02776 void SimpleRegisterCoalescing::print(std::ostream &O, const Module* m) const { 02777 li_->print(O, m); 02778 } 02779 02780 RegisterCoalescer* llvm::createSimpleRegisterCoalescer() { 02781 return new SimpleRegisterCoalescing(); 02782 } 02783 02784 // Make sure that anything that uses RegisterCoalescer pulls in this file... 02785 DEFINING_FILE_FOR(SimpleRegisterCoalescing)