StackSlotColoring.cpp revision 1edf7ee80259c8a99c5544405cb2746443fab832
1//===-- StackSlotColoring.cpp - Stack slot coloring pass. -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the stack slot coloring pass. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "stackcoloring" 15#include "llvm/CodeGen/Passes.h" 16#include "llvm/CodeGen/LiveStackAnalysis.h" 17#include "llvm/CodeGen/MachineFrameInfo.h" 18#include "llvm/CodeGen/PseudoSourceValue.h" 19#include "llvm/Support/CommandLine.h" 20#include "llvm/Support/Compiler.h" 21#include "llvm/Support/Debug.h" 22#include "llvm/Target/TargetInstrInfo.h" 23#include "llvm/Target/TargetMachine.h" 24#include "llvm/ADT/BitVector.h" 25#include "llvm/ADT/SmallVector.h" 26#include "llvm/ADT/Statistic.h" 27#include <vector> 28using namespace llvm; 29 30static cl::opt<bool> 31DisableSharing("no-stack-slot-sharing", 32 cl::init(false), cl::Hidden, 33 cl::desc("Surpress slot sharing during stack coloring")); 34 35static cl::opt<bool> 36EnableDCE("enable-ssc-dce", 37 cl::init(false), cl::Hidden, 38 cl::desc("Enable slot coloring DCE")); 39 40STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); 41STATISTIC(NumDeadAccesses, 42 "Number of trivially dead stack accesses eliminated"); 43 44namespace { 45 class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass { 46 LiveStacks* LS; 47 MachineFrameInfo *MFI; 48 const TargetInstrInfo *TII; 49 50 // SSIntervals - Spill slot intervals. 51 std::vector<LiveInterval*> SSIntervals; 52 53 // OrigAlignments - Alignments of stack objects before coloring. 54 SmallVector<unsigned, 16> OrigAlignments; 55 56 // OrigSizes - Sizess of stack objects before coloring. 57 SmallVector<unsigned, 16> OrigSizes; 58 59 // AllColors - If index is set, it's a spill slot, i.e. color. 60 // FIXME: This assumes PEI locate spill slot with smaller indices 61 // closest to stack pointer / frame pointer. Therefore, smaller 62 // index == better color. 63 BitVector AllColors; 64 65 // NextColor - Next "color" that's not yet used. 66 int NextColor; 67 68 // UsedColors - "Colors" that have been assigned. 69 BitVector UsedColors; 70 71 // Assignments - Color to intervals mapping. 72 SmallVector<SmallVector<LiveInterval*,4>,16> Assignments; 73 74 public: 75 static char ID; // Pass identification 76 StackSlotColoring() : MachineFunctionPass(&ID), NextColor(-1) {} 77 78 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 79 AU.addRequired<LiveStacks>(); 80 81 AU.addPreservedID(MachineLoopInfoID); 82 AU.addPreservedID(MachineDominatorsID); 83 MachineFunctionPass::getAnalysisUsage(AU); 84 } 85 86 virtual bool runOnMachineFunction(MachineFunction &MF); 87 virtual const char* getPassName() const { 88 return "Stack Slot Coloring"; 89 } 90 91 private: 92 bool InitializeSlots(); 93 bool OverlapWithAssignments(LiveInterval *li, int Color) const; 94 int ColorSlot(LiveInterval *li); 95 bool ColorSlots(MachineFunction &MF); 96 bool removeDeadStores(MachineBasicBlock* MBB); 97 }; 98} // end anonymous namespace 99 100char StackSlotColoring::ID = 0; 101 102static RegisterPass<StackSlotColoring> 103X("stack-slot-coloring", "Stack Slot Coloring"); 104 105FunctionPass *llvm::createStackSlotColoringPass() { 106 return new StackSlotColoring(); 107} 108 109namespace { 110 // IntervalSorter - Comparison predicate that sort live intervals by 111 // their weight. 112 struct IntervalSorter { 113 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 114 return LHS->weight > RHS->weight; 115 } 116 }; 117} 118 119/// InitializeSlots - Process all spill stack slot liveintervals and add them 120/// to a sorted (by weight) list. 121bool StackSlotColoring::InitializeSlots() { 122 if (LS->getNumIntervals() < 2) 123 return false; 124 125 int LastFI = MFI->getObjectIndexEnd(); 126 OrigAlignments.resize(LastFI); 127 OrigSizes.resize(LastFI); 128 AllColors.resize(LastFI); 129 UsedColors.resize(LastFI); 130 Assignments.resize(LastFI); 131 132 // Gather all spill slots into a list. 133 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 134 LiveInterval &li = i->second; 135 int FI = li.getStackSlotIndex(); 136 if (MFI->isDeadObjectIndex(FI)) 137 continue; 138 SSIntervals.push_back(&li); 139 OrigAlignments[FI] = MFI->getObjectAlignment(FI); 140 OrigSizes[FI] = MFI->getObjectSize(FI); 141 AllColors.set(FI); 142 } 143 144 // Sort them by weight. 145 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 146 147 // Get first "color". 148 NextColor = AllColors.find_first(); 149 return true; 150} 151 152/// OverlapWithAssignments - Return true if LiveInterval overlaps with any 153/// LiveIntervals that have already been assigned to the specified color. 154bool 155StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 156 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; 157 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 158 LiveInterval *OtherLI = OtherLIs[i]; 159 if (OtherLI->overlaps(*li)) 160 return true; 161 } 162 return false; 163} 164 165/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 166/// 167int StackSlotColoring::ColorSlot(LiveInterval *li) { 168 int Color = -1; 169 bool Share = false; 170 if (!DisableSharing) { 171 // Check if it's possible to reuse any of the used colors. 172 Color = UsedColors.find_first(); 173 while (Color != -1) { 174 if (!OverlapWithAssignments(li, Color)) { 175 Share = true; 176 ++NumEliminated; 177 break; 178 } 179 Color = UsedColors.find_next(Color); 180 } 181 } 182 183 // Assign it to the first available color (assumed to be the best) if it's 184 // not possible to share a used color with other objects. 185 if (!Share) { 186 assert(NextColor != -1 && "No more spill slots?"); 187 Color = NextColor; 188 UsedColors.set(Color); 189 NextColor = AllColors.find_next(NextColor); 190 } 191 192 // Record the assignment. 193 Assignments[Color].push_back(li); 194 int FI = li->getStackSlotIndex(); 195 DOUT << "Assigning fi#" << FI << " to fi#" << Color << "\n"; 196 197 // Change size and alignment of the allocated slot. If there are multiple 198 // objects sharing the same slot, then make sure the size and alignment 199 // are large enough for all. 200 unsigned Align = OrigAlignments[FI]; 201 if (!Share || Align > MFI->getObjectAlignment(Color)) 202 MFI->setObjectAlignment(Color, Align); 203 int64_t Size = OrigSizes[FI]; 204 if (!Share || Size > MFI->getObjectSize(Color)) 205 MFI->setObjectSize(Color, Size); 206 return Color; 207} 208 209/// Colorslots - Color all spill stack slots and rewrite all frameindex machine 210/// operands in the function. 211bool StackSlotColoring::ColorSlots(MachineFunction &MF) { 212 unsigned NumObjs = MFI->getObjectIndexEnd(); 213 std::vector<int> SlotMapping(NumObjs, -1); 214 215 bool Changed = false; 216 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 217 LiveInterval *li = SSIntervals[i]; 218 int SS = li->getStackSlotIndex(); 219 int NewSS = ColorSlot(li); 220 SlotMapping[SS] = NewSS; 221 Changed |= (SS != NewSS); 222 } 223 224 if (!Changed) 225 return false; 226 227 // Rewrite all MO_FrameIndex operands. 228 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 229 for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); 230 MBB != E; ++MBB) { 231 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 232 MII != EE; ++MII) { 233 MachineInstr &MI = *MII; 234 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 235 MachineOperand &MO = MI.getOperand(i); 236 if (!MO.isFI()) 237 continue; 238 int FI = MO.getIndex(); 239 if (FI < 0) 240 continue; 241 int NewFI = SlotMapping[FI]; 242 if (NewFI == -1) 243 continue; 244 MO.setIndex(NewFI); 245 246 // Update the MachineMemOperand for the new memory location. 247 // FIXME: We need a better method of managing these too. 248 SmallVector<MachineMemOperand, 2> MMOs(MI.memoperands_begin(), 249 MI.memoperands_end()); 250 MI.clearMemOperands(MF); 251 const Value *OldSV = PseudoSourceValue::getFixedStack(FI); 252 for (unsigned i = 0, e = MMOs.size(); i != e; ++i) { 253 if (MMOs[i].getValue() == OldSV) { 254 MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI), 255 MMOs[i].getFlags(), MMOs[i].getOffset(), 256 MMOs[i].getSize(), MMOs[i].getAlignment()); 257 MI.addMemOperand(MF, MMO); 258 } else 259 MI.addMemOperand(MF, MMOs[i]); 260 } 261 } 262 } 263 } 264 265 // Delete unused stack slots. 266 while (NextColor != -1) { 267 DOUT << "Removing unused stack object fi#" << NextColor << "\n"; 268 MFI->RemoveStackObject(NextColor); 269 NextColor = AllColors.find_next(NextColor); 270 } 271 272 return true; 273} 274 275/// removeDeadStores - Scan through a basic block and look for loads followed 276/// by stores. If they're both using the same stack slot, then the store is 277/// definitely dead. This could obviously be much more aggressive (consider 278/// pairs with instructions between them), but such extensions might have a 279/// considerable compile time impact. 280bool StackSlotColoring::removeDeadStores(MachineBasicBlock* MBB) { 281 // FIXME: This could be much more aggressive, but we need to investigate 282 // the compile time impact of doing so. 283 bool changed = false; 284 285 SmallVector<MachineInstr*, 4> toErase; 286 287 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 288 I != E; ++I) { 289 MachineBasicBlock::iterator NextMI = next(I); 290 if (NextMI == MBB->end()) continue; 291 292 int FirstSS, SecondSS; 293 unsigned LoadReg = 0; 294 unsigned StoreReg = 0; 295 if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue; 296 if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue; 297 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue; 298 299 ++NumDeadAccesses; 300 changed = true; 301 302 if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { 303 ++NumDeadAccesses; 304 toErase.push_back(I); 305 } 306 307 toErase.push_back(NextMI); 308 ++I; 309 } 310 311 for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(), 312 E = toErase.end(); I != E; ++I) 313 (*I)->eraseFromParent(); 314 315 return changed; 316} 317 318 319bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 320 DOUT << "********** Stack Slot Coloring **********\n"; 321 322 MFI = MF.getFrameInfo(); 323 TII = MF.getTarget().getInstrInfo(); 324 LS = &getAnalysis<LiveStacks>(); 325 326 bool Changed = false; 327 if (InitializeSlots()) 328 Changed = ColorSlots(MF); 329 330 NextColor = -1; 331 SSIntervals.clear(); 332 OrigAlignments.clear(); 333 OrigSizes.clear(); 334 AllColors.clear(); 335 UsedColors.clear(); 336 for (unsigned i = 0, e = Assignments.size(); i != e; ++i) 337 Assignments[i].clear(); 338 Assignments.clear(); 339 340 if (EnableDCE) { 341 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 342 Changed |= removeDeadStores(I); 343 } 344 345 return Changed; 346} 347