LLVM API Documentation
00001 //===-- StackSlotColoring.cpp - Stack slot coloring pass. -----------------===// 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 the stack slot coloring pass. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "stackcoloring" 00015 #include "VirtRegMap.h" 00016 #include "llvm/CodeGen/Passes.h" 00017 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 00018 #include "llvm/CodeGen/LiveStackAnalysis.h" 00019 #include "llvm/CodeGen/MachineFrameInfo.h" 00020 #include "llvm/CodeGen/MachineLoopInfo.h" 00021 #include "llvm/CodeGen/MachineRegisterInfo.h" 00022 #include "llvm/CodeGen/PseudoSourceValue.h" 00023 #include "llvm/Support/CommandLine.h" 00024 #include "llvm/Support/Compiler.h" 00025 #include "llvm/Support/Debug.h" 00026 #include "llvm/Target/TargetInstrInfo.h" 00027 #include "llvm/Target/TargetMachine.h" 00028 #include "llvm/ADT/BitVector.h" 00029 #include "llvm/ADT/SmallSet.h" 00030 #include "llvm/ADT/SmallVector.h" 00031 #include "llvm/ADT/Statistic.h" 00032 #include <vector> 00033 using namespace llvm; 00034 00035 static cl::opt<bool> 00036 DisableSharing("no-stack-slot-sharing", 00037 cl::init(false), cl::Hidden, 00038 cl::desc("Suppress slot sharing during stack coloring")); 00039 00040 static cl::opt<bool> 00041 ColorWithRegsOpt("color-ss-with-regs", 00042 cl::init(false), cl::Hidden, 00043 cl::desc("Color stack slots with free registers")); 00044 00045 00046 static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); 00047 00048 STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); 00049 STATISTIC(NumRegRepl, "Number of stack slot refs replaced with reg refs"); 00050 STATISTIC(NumLoadElim, "Number of loads eliminated"); 00051 STATISTIC(NumStoreElim, "Number of stores eliminated"); 00052 STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); 00053 00054 namespace { 00055 class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass { 00056 bool ColorWithRegs; 00057 LiveStacks* LS; 00058 VirtRegMap* VRM; 00059 MachineFrameInfo *MFI; 00060 MachineRegisterInfo *MRI; 00061 const TargetInstrInfo *TII; 00062 const TargetRegisterInfo *TRI; 00063 const MachineLoopInfo *loopInfo; 00064 00065 // SSIntervals - Spill slot intervals. 00066 std::vector<LiveInterval*> SSIntervals; 00067 00068 // SSRefs - Keep a list of frame index references for each spill slot. 00069 SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs; 00070 00071 // OrigAlignments - Alignments of stack objects before coloring. 00072 SmallVector<unsigned, 16> OrigAlignments; 00073 00074 // OrigSizes - Sizess of stack objects before coloring. 00075 SmallVector<unsigned, 16> OrigSizes; 00076 00077 // AllColors - If index is set, it's a spill slot, i.e. color. 00078 // FIXME: This assumes PEI locate spill slot with smaller indices 00079 // closest to stack pointer / frame pointer. Therefore, smaller 00080 // index == better color. 00081 BitVector AllColors; 00082 00083 // NextColor - Next "color" that's not yet used. 00084 int NextColor; 00085 00086 // UsedColors - "Colors" that have been assigned. 00087 BitVector UsedColors; 00088 00089 // Assignments - Color to intervals mapping. 00090 SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments; 00091 00092 public: 00093 static char ID; // Pass identification 00094 StackSlotColoring() : 00095 MachineFunctionPass(&ID), ColorWithRegs(false), NextColor(-1) {} 00096 StackSlotColoring(bool RegColor) : 00097 MachineFunctionPass(&ID), ColorWithRegs(RegColor), NextColor(-1) {} 00098 00099 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00100 AU.setPreservesCFG(); 00101 AU.addRequired<LiveStacks>(); 00102 AU.addRequired<VirtRegMap>(); 00103 AU.addPreserved<VirtRegMap>(); 00104 AU.addRequired<MachineLoopInfo>(); 00105 AU.addPreserved<MachineLoopInfo>(); 00106 AU.addPreservedID(MachineDominatorsID); 00107 MachineFunctionPass::getAnalysisUsage(AU); 00108 } 00109 00110 virtual bool runOnMachineFunction(MachineFunction &MF); 00111 virtual const char* getPassName() const { 00112 return "Stack Slot Coloring"; 00113 } 00114 00115 private: 00116 void InitializeSlots(); 00117 void ScanForSpillSlotRefs(MachineFunction &MF); 00118 bool OverlapWithAssignments(LiveInterval *li, int Color) const; 00119 int ColorSlot(LiveInterval *li); 00120 bool ColorSlots(MachineFunction &MF); 00121 bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, 00122 SmallVector<SmallVector<int, 4>, 16> &RevMap, 00123 BitVector &SlotIsReg); 00124 void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI, 00125 MachineFunction &MF); 00126 bool PropagateBackward(MachineBasicBlock::iterator MII, 00127 MachineBasicBlock *MBB, 00128 unsigned OldReg, unsigned NewReg); 00129 bool PropagateForward(MachineBasicBlock::iterator MII, 00130 MachineBasicBlock *MBB, 00131 unsigned OldReg, unsigned NewReg); 00132 void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, 00133 unsigned Reg, const TargetRegisterClass *RC, 00134 SmallSet<unsigned, 4> &Defs, 00135 MachineFunction &MF); 00136 bool AllMemRefsCanBeUnfolded(int SS); 00137 bool RemoveDeadStores(MachineBasicBlock* MBB); 00138 }; 00139 } // end anonymous namespace 00140 00141 char StackSlotColoring::ID = 0; 00142 00143 static RegisterPass<StackSlotColoring> 00144 X("stack-slot-coloring", "Stack Slot Coloring"); 00145 00146 FunctionPass *llvm::createStackSlotColoringPass(bool RegColor) { 00147 return new StackSlotColoring(RegColor); 00148 } 00149 00150 namespace { 00151 // IntervalSorter - Comparison predicate that sort live intervals by 00152 // their weight. 00153 struct IntervalSorter { 00154 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 00155 return LHS->weight > RHS->weight; 00156 } 00157 }; 00158 } 00159 00160 /// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot 00161 /// references and update spill slot weights. 00162 void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { 00163 SSRefs.resize(MFI->getObjectIndexEnd()); 00164 00165 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 00166 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 00167 MBBI != E; ++MBBI) { 00168 MachineBasicBlock *MBB = &*MBBI; 00169 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 00170 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 00171 MII != EE; ++MII) { 00172 MachineInstr *MI = &*MII; 00173 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00174 MachineOperand &MO = MI->getOperand(i); 00175 if (!MO.isFI()) 00176 continue; 00177 int FI = MO.getIndex(); 00178 if (FI < 0) 00179 continue; 00180 if (!LS->hasInterval(FI)) 00181 continue; 00182 LiveInterval &li = LS->getInterval(FI); 00183 li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth); 00184 SSRefs[FI].push_back(MI); 00185 } 00186 } 00187 } 00188 } 00189 00190 /// InitializeSlots - Process all spill stack slot liveintervals and add them 00191 /// to a sorted (by weight) list. 00192 void StackSlotColoring::InitializeSlots() { 00193 int LastFI = MFI->getObjectIndexEnd(); 00194 OrigAlignments.resize(LastFI); 00195 OrigSizes.resize(LastFI); 00196 AllColors.resize(LastFI); 00197 UsedColors.resize(LastFI); 00198 Assignments.resize(LastFI); 00199 00200 // Gather all spill slots into a list. 00201 DOUT << "Spill slot intervals:\n"; 00202 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 00203 LiveInterval &li = i->second; 00204 DEBUG(li.dump()); 00205 int FI = li.getStackSlotIndex(); 00206 if (MFI->isDeadObjectIndex(FI)) 00207 continue; 00208 SSIntervals.push_back(&li); 00209 OrigAlignments[FI] = MFI->getObjectAlignment(FI); 00210 OrigSizes[FI] = MFI->getObjectSize(FI); 00211 AllColors.set(FI); 00212 } 00213 DOUT << '\n'; 00214 00215 // Sort them by weight. 00216 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 00217 00218 // Get first "color". 00219 NextColor = AllColors.find_first(); 00220 } 00221 00222 /// OverlapWithAssignments - Return true if LiveInterval overlaps with any 00223 /// LiveIntervals that have already been assigned to the specified color. 00224 bool 00225 StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 00226 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; 00227 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 00228 LiveInterval *OtherLI = OtherLIs[i]; 00229 if (OtherLI->overlaps(*li)) 00230 return true; 00231 } 00232 return false; 00233 } 00234 00235 /// ColorSlotsWithFreeRegs - If there are any free registers available, try 00236 /// replacing spill slots references with registers instead. 00237 bool 00238 StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, 00239 SmallVector<SmallVector<int, 4>, 16> &RevMap, 00240 BitVector &SlotIsReg) { 00241 if (!(ColorWithRegs || ColorWithRegsOpt) || !VRM->HasUnusedRegisters()) 00242 return false; 00243 00244 bool Changed = false; 00245 DOUT << "Assigning unused registers to spill slots:\n"; 00246 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 00247 LiveInterval *li = SSIntervals[i]; 00248 int SS = li->getStackSlotIndex(); 00249 if (!UsedColors[SS] || li->weight < 20) 00250 // If the weight is < 20, i.e. two references in a loop with depth 1, 00251 // don't bother with it. 00252 continue; 00253 00254 // These slots allow to share the same registers. 00255 bool AllColored = true; 00256 SmallVector<unsigned, 4> ColoredRegs; 00257 for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { 00258 int RSS = RevMap[SS][j]; 00259 const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS); 00260 // If it's not colored to another stack slot, try coloring it 00261 // to a "free" register. 00262 if (!RC) { 00263 AllColored = false; 00264 continue; 00265 } 00266 unsigned Reg = VRM->getFirstUnusedRegister(RC); 00267 if (!Reg) { 00268 AllColored = false; 00269 continue; 00270 } 00271 if (!AllMemRefsCanBeUnfolded(RSS)) { 00272 AllColored = false; 00273 continue; 00274 } else { 00275 DOUT << "Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n'; 00276 ColoredRegs.push_back(Reg); 00277 SlotMapping[RSS] = Reg; 00278 SlotIsReg.set(RSS); 00279 Changed = true; 00280 } 00281 } 00282 00283 // Register and its sub-registers are no longer free. 00284 while (!ColoredRegs.empty()) { 00285 unsigned Reg = ColoredRegs.back(); 00286 ColoredRegs.pop_back(); 00287 VRM->setRegisterUsed(Reg); 00288 // If reg is a callee-saved register, it will have to be spilled in 00289 // the prologue. 00290 MRI->setPhysRegUsed(Reg); 00291 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 00292 VRM->setRegisterUsed(*AS); 00293 MRI->setPhysRegUsed(*AS); 00294 } 00295 } 00296 // This spill slot is dead after the rewrites 00297 if (AllColored) { 00298 MFI->RemoveStackObject(SS); 00299 ++NumEliminated; 00300 } 00301 } 00302 DOUT << '\n'; 00303 00304 return Changed; 00305 } 00306 00307 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 00308 /// 00309 int StackSlotColoring::ColorSlot(LiveInterval *li) { 00310 int Color = -1; 00311 bool Share = false; 00312 if (!DisableSharing) { 00313 // Check if it's possible to reuse any of the used colors. 00314 Color = UsedColors.find_first(); 00315 while (Color != -1) { 00316 if (!OverlapWithAssignments(li, Color)) { 00317 Share = true; 00318 ++NumEliminated; 00319 break; 00320 } 00321 Color = UsedColors.find_next(Color); 00322 } 00323 } 00324 00325 // Assign it to the first available color (assumed to be the best) if it's 00326 // not possible to share a used color with other objects. 00327 if (!Share) { 00328 assert(NextColor != -1 && "No more spill slots?"); 00329 Color = NextColor; 00330 UsedColors.set(Color); 00331 NextColor = AllColors.find_next(NextColor); 00332 } 00333 00334 // Record the assignment. 00335 Assignments[Color].push_back(li); 00336 int FI = li->getStackSlotIndex(); 00337 DOUT << "Assigning fi#" << FI << " to fi#" << Color << "\n"; 00338 00339 // Change size and alignment of the allocated slot. If there are multiple 00340 // objects sharing the same slot, then make sure the size and alignment 00341 // are large enough for all. 00342 unsigned Align = OrigAlignments[FI]; 00343 if (!Share || Align > MFI->getObjectAlignment(Color)) 00344 MFI->setObjectAlignment(Color, Align); 00345 int64_t Size = OrigSizes[FI]; 00346 if (!Share || Size > MFI->getObjectSize(Color)) 00347 MFI->setObjectSize(Color, Size); 00348 return Color; 00349 } 00350 00351 /// Colorslots - Color all spill stack slots and rewrite all frameindex machine 00352 /// operands in the function. 00353 bool StackSlotColoring::ColorSlots(MachineFunction &MF) { 00354 unsigned NumObjs = MFI->getObjectIndexEnd(); 00355 SmallVector<int, 16> SlotMapping(NumObjs, -1); 00356 SmallVector<float, 16> SlotWeights(NumObjs, 0.0); 00357 SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs); 00358 BitVector SlotIsReg(NumObjs); 00359 BitVector UsedColors(NumObjs); 00360 00361 DOUT << "Color spill slot intervals:\n"; 00362 bool Changed = false; 00363 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 00364 LiveInterval *li = SSIntervals[i]; 00365 int SS = li->getStackSlotIndex(); 00366 int NewSS = ColorSlot(li); 00367 assert(NewSS >= 0 && "Stack coloring failed?"); 00368 SlotMapping[SS] = NewSS; 00369 RevMap[NewSS].push_back(SS); 00370 SlotWeights[NewSS] += li->weight; 00371 UsedColors.set(NewSS); 00372 Changed |= (SS != NewSS); 00373 } 00374 00375 DOUT << "\nSpill slots after coloring:\n"; 00376 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 00377 LiveInterval *li = SSIntervals[i]; 00378 int SS = li->getStackSlotIndex(); 00379 li->weight = SlotWeights[SS]; 00380 } 00381 // Sort them by new weight. 00382 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 00383 00384 #ifndef NDEBUG 00385 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) 00386 DEBUG(SSIntervals[i]->dump()); 00387 DOUT << '\n'; 00388 #endif 00389 00390 // Can we "color" a stack slot with a unused register? 00391 Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg); 00392 00393 if (!Changed) 00394 return false; 00395 00396 // Rewrite all MO_FrameIndex operands. 00397 SmallVector<SmallSet<unsigned, 4>, 4> NewDefs(MF.getNumBlockIDs()); 00398 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { 00399 bool isReg = SlotIsReg[SS]; 00400 int NewFI = SlotMapping[SS]; 00401 if (NewFI == -1 || (NewFI == (int)SS && !isReg)) 00402 continue; 00403 00404 const TargetRegisterClass *RC = LS->getIntervalRegClass(SS); 00405 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 00406 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) 00407 if (!isReg) 00408 RewriteInstruction(RefMIs[i], SS, NewFI, MF); 00409 else { 00410 // Rewrite to use a register instead. 00411 unsigned MBBId = RefMIs[i]->getParent()->getNumber(); 00412 SmallSet<unsigned, 4> &Defs = NewDefs[MBBId]; 00413 UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, RC, Defs, MF); 00414 } 00415 } 00416 00417 // Delete unused stack slots. 00418 while (NextColor != -1) { 00419 DOUT << "Removing unused stack object fi#" << NextColor << "\n"; 00420 MFI->RemoveStackObject(NextColor); 00421 NextColor = AllColors.find_next(NextColor); 00422 } 00423 00424 return true; 00425 } 00426 00427 /// AllMemRefsCanBeUnfolded - Return true if all references of the specified 00428 /// spill slot index can be unfolded. 00429 bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) { 00430 SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 00431 for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) { 00432 MachineInstr *MI = RefMIs[i]; 00433 if (TII->isLoadFromStackSlot(MI, SS) || 00434 TII->isStoreToStackSlot(MI, SS)) 00435 // Restore and spill will become copies. 00436 return true; 00437 if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false)) 00438 return false; 00439 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 00440 MachineOperand &MO = MI->getOperand(j); 00441 if (MO.isFI() && MO.getIndex() != SS) 00442 // If it uses another frameindex, we can, currently* unfold it. 00443 return false; 00444 } 00445 } 00446 return true; 00447 } 00448 00449 /// RewriteInstruction - Rewrite specified instruction by replacing references 00450 /// to old frame index with new one. 00451 void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI, 00452 int NewFI, MachineFunction &MF) { 00453 for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) { 00454 MachineOperand &MO = MI->getOperand(i); 00455 if (!MO.isFI()) 00456 continue; 00457 int FI = MO.getIndex(); 00458 if (FI != OldFI) 00459 continue; 00460 MO.setIndex(NewFI); 00461 } 00462 00463 // Update the MachineMemOperand for the new memory location. 00464 // FIXME: We need a better method of managing these too. 00465 SmallVector<MachineMemOperand, 2> MMOs(MI->memoperands_begin(), 00466 MI->memoperands_end()); 00467 MI->clearMemOperands(MF); 00468 const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI); 00469 for (unsigned i = 0, ee = MMOs.size(); i != ee; ++i) { 00470 if (MMOs[i].getValue() != OldSV) 00471 MI->addMemOperand(MF, MMOs[i]); 00472 else { 00473 MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI), 00474 MMOs[i].getFlags(), MMOs[i].getOffset(), 00475 MMOs[i].getSize(), MMOs[i].getAlignment()); 00476 MI->addMemOperand(MF, MMO); 00477 } 00478 } 00479 } 00480 00481 /// PropagateBackward - Traverse backward and look for the definition of 00482 /// OldReg. If it can successfully update all of the references with NewReg, 00483 /// do so and return true. 00484 bool StackSlotColoring::PropagateBackward(MachineBasicBlock::iterator MII, 00485 MachineBasicBlock *MBB, 00486 unsigned OldReg, unsigned NewReg) { 00487 if (MII == MBB->begin()) 00488 return false; 00489 00490 SmallVector<MachineOperand*, 4> Uses; 00491 SmallVector<MachineOperand*, 4> Refs; 00492 while (--MII != MBB->begin()) { 00493 bool FoundDef = false; // Not counting 2address def. 00494 00495 Uses.clear(); 00496 const TargetInstrDesc &TID = MII->getDesc(); 00497 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 00498 MachineOperand &MO = MII->getOperand(i); 00499 if (!MO.isReg()) 00500 continue; 00501 unsigned Reg = MO.getReg(); 00502 if (Reg == 0) 00503 continue; 00504 if (Reg == OldReg) { 00505 if (MO.isImplicit()) 00506 return false; 00507 00508 // Abort the use is actually a sub-register def. We don't have enough 00509 // information to figure out if it is really legal. 00510 if (MO.getSubReg() || 00511 TID.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 00512 TID.getOpcode() == TargetInstrInfo::INSERT_SUBREG || 00513 TID.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 00514 return false; 00515 00516 const TargetRegisterClass *RC = TID.OpInfo[i].getRegClass(TRI); 00517 if (RC && !RC->contains(NewReg)) 00518 return false; 00519 00520 if (MO.isUse()) { 00521 Uses.push_back(&MO); 00522 } else { 00523 Refs.push_back(&MO); 00524 if (!MII->isRegTiedToUseOperand(i)) 00525 FoundDef = true; 00526 } 00527 } else if (TRI->regsOverlap(Reg, NewReg)) { 00528 return false; 00529 } else if (TRI->regsOverlap(Reg, OldReg)) { 00530 if (!MO.isUse() || !MO.isKill()) 00531 return false; 00532 } 00533 } 00534 00535 if (FoundDef) { 00536 // Found non-two-address def. Stop here. 00537 for (unsigned i = 0, e = Refs.size(); i != e; ++i) 00538 Refs[i]->setReg(NewReg); 00539 return true; 00540 } 00541 00542 // Two-address uses must be updated as well. 00543 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 00544 Refs.push_back(Uses[i]); 00545 } 00546 return false; 00547 } 00548 00549 /// PropagateForward - Traverse forward and look for the kill of OldReg. If 00550 /// it can successfully update all of the uses with NewReg, do so and 00551 /// return true. 00552 bool StackSlotColoring::PropagateForward(MachineBasicBlock::iterator MII, 00553 MachineBasicBlock *MBB, 00554 unsigned OldReg, unsigned NewReg) { 00555 if (MII == MBB->end()) 00556 return false; 00557 00558 SmallVector<MachineOperand*, 4> Uses; 00559 while (++MII != MBB->end()) { 00560 bool FoundUse = false; 00561 bool FoundKill = false; 00562 const TargetInstrDesc &TID = MII->getDesc(); 00563 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 00564 MachineOperand &MO = MII->getOperand(i); 00565 if (!MO.isReg()) 00566 continue; 00567 unsigned Reg = MO.getReg(); 00568 if (Reg == 0) 00569 continue; 00570 if (Reg == OldReg) { 00571 if (MO.isDef() || MO.isImplicit()) 00572 return false; 00573 00574 // Abort the use is actually a sub-register use. We don't have enough 00575 // information to figure out if it is really legal. 00576 if (MO.getSubReg() || 00577 TID.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 00578 return false; 00579 00580 const TargetRegisterClass *RC = TID.OpInfo[i].getRegClass(TRI); 00581 if (RC && !RC->contains(NewReg)) 00582 return false; 00583 FoundUse = true; 00584 if (MO.isKill()) 00585 FoundKill = true; 00586 00587 Uses.push_back(&MO); 00588 } else if (TRI->regsOverlap(Reg, NewReg) || 00589 TRI->regsOverlap(Reg, OldReg)) 00590 return false; 00591 } 00592 if (FoundKill) { 00593 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 00594 Uses[i]->setReg(NewReg); 00595 return true; 00596 } 00597 } 00598 return false; 00599 } 00600 00601 /// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding 00602 /// folded memory references and replacing those references with register 00603 /// references instead. 00604 void 00605 StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, 00606 unsigned Reg, 00607 const TargetRegisterClass *RC, 00608 SmallSet<unsigned, 4> &Defs, 00609 MachineFunction &MF) { 00610 MachineBasicBlock *MBB = MI->getParent(); 00611 if (unsigned DstReg = TII->isLoadFromStackSlot(MI, OldFI)) { 00612 if (PropagateForward(MI, MBB, DstReg, Reg)) { 00613 DOUT << "Eliminated load: "; 00614 DEBUG(MI->dump()); 00615 ++NumLoadElim; 00616 } else { 00617 TII->copyRegToReg(*MBB, MI, DstReg, Reg, RC, RC); 00618 ++NumRegRepl; 00619 } 00620 00621 if (!Defs.count(Reg)) { 00622 // If this is the first use of Reg in this MBB and it wasn't previously 00623 // defined in MBB, add it to livein. 00624 MBB->addLiveIn(Reg); 00625 Defs.insert(Reg); 00626 } 00627 } else if (unsigned SrcReg = TII->isStoreToStackSlot(MI, OldFI)) { 00628 if (MI->killsRegister(SrcReg) && PropagateBackward(MI, MBB, SrcReg, Reg)) { 00629 DOUT << "Eliminated store: "; 00630 DEBUG(MI->dump()); 00631 ++NumStoreElim; 00632 } else { 00633 TII->copyRegToReg(*MBB, MI, Reg, SrcReg, RC, RC); 00634 ++NumRegRepl; 00635 } 00636 00637 // Remember reg has been defined in MBB. 00638 Defs.insert(Reg); 00639 } else { 00640 SmallVector<MachineInstr*, 4> NewMIs; 00641 bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs); 00642 Success = Success; // Silence compiler warning. 00643 assert(Success && "Failed to unfold!"); 00644 MachineInstr *NewMI = NewMIs[0]; 00645 MBB->insert(MI, NewMI); 00646 ++NumRegRepl; 00647 00648 if (NewMI->readsRegister(Reg)) { 00649 if (!Defs.count(Reg)) 00650 // If this is the first use of Reg in this MBB and it wasn't previously 00651 // defined in MBB, add it to livein. 00652 MBB->addLiveIn(Reg); 00653 Defs.insert(Reg); 00654 } 00655 } 00656 MBB->erase(MI); 00657 } 00658 00659 /// RemoveDeadStores - Scan through a basic block and look for loads followed 00660 /// by stores. If they're both using the same stack slot, then the store is 00661 /// definitely dead. This could obviously be much more aggressive (consider 00662 /// pairs with instructions between them), but such extensions might have a 00663 /// considerable compile time impact. 00664 bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { 00665 // FIXME: This could be much more aggressive, but we need to investigate 00666 // the compile time impact of doing so. 00667 bool changed = false; 00668 00669 SmallVector<MachineInstr*, 4> toErase; 00670 00671 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 00672 I != E; ++I) { 00673 if (DCELimit != -1 && (int)NumDead >= DCELimit) 00674 break; 00675 00676 MachineBasicBlock::iterator NextMI = next(I); 00677 if (NextMI == MBB->end()) continue; 00678 00679 int FirstSS, SecondSS; 00680 unsigned LoadReg = 0; 00681 unsigned StoreReg = 0; 00682 if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue; 00683 if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue; 00684 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue; 00685 00686 ++NumDead; 00687 changed = true; 00688 00689 if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { 00690 ++NumDead; 00691 toErase.push_back(I); 00692 } 00693 00694 toErase.push_back(NextMI); 00695 ++I; 00696 } 00697 00698 for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(), 00699 E = toErase.end(); I != E; ++I) 00700 (*I)->eraseFromParent(); 00701 00702 return changed; 00703 } 00704 00705 00706 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 00707 DOUT << "********** Stack Slot Coloring **********\n"; 00708 00709 MFI = MF.getFrameInfo(); 00710 MRI = &MF.getRegInfo(); 00711 TII = MF.getTarget().getInstrInfo(); 00712 TRI = MF.getTarget().getRegisterInfo(); 00713 LS = &getAnalysis<LiveStacks>(); 00714 VRM = &getAnalysis<VirtRegMap>(); 00715 loopInfo = &getAnalysis<MachineLoopInfo>(); 00716 00717 bool Changed = false; 00718 00719 unsigned NumSlots = LS->getNumIntervals(); 00720 if (NumSlots < 2) { 00721 if (NumSlots == 0 || !VRM->HasUnusedRegisters()) 00722 // Nothing to do! 00723 return false; 00724 } 00725 00726 // Gather spill slot references 00727 ScanForSpillSlotRefs(MF); 00728 InitializeSlots(); 00729 Changed = ColorSlots(MF); 00730 00731 NextColor = -1; 00732 SSIntervals.clear(); 00733 for (unsigned i = 0, e = SSRefs.size(); i != e; ++i) 00734 SSRefs[i].clear(); 00735 SSRefs.clear(); 00736 OrigAlignments.clear(); 00737 OrigSizes.clear(); 00738 AllColors.clear(); 00739 UsedColors.clear(); 00740 for (unsigned i = 0, e = Assignments.size(); i != e; ++i) 00741 Assignments[i].clear(); 00742 Assignments.clear(); 00743 00744 if (Changed) { 00745 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 00746 Changed |= RemoveDeadStores(I); 00747 } 00748 00749 return Changed; 00750 }