StackSlotColoring.cpp revision ae73dc1448d25b02cabc7c64c86c64371453dda8
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/Support/CommandLine.h" 19#include "llvm/Support/Compiler.h" 20#include "llvm/Support/Debug.h" 21#include "llvm/ADT/BitVector.h" 22#include "llvm/ADT/SmallVector.h" 23#include "llvm/ADT/Statistic.h" 24#include <vector> 25using namespace llvm; 26 27static cl::opt<bool> 28DisableSharing("no-stack-slot-sharing", 29 cl::init(false), cl::Hidden, 30 cl::desc("Surpress slot sharing during stack coloring")); 31 32STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); 33 34namespace { 35 class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass { 36 LiveStacks* LS; 37 MachineFrameInfo *MFI; 38 39 // SSIntervals - Spill slot intervals. 40 std::vector<LiveInterval*> SSIntervals; 41 42 // OrigAlignments - Alignments of stack objects before coloring. 43 SmallVector<unsigned, 16> OrigAlignments; 44 45 // OrigSizes - Sizess of stack objects before coloring. 46 SmallVector<unsigned, 16> OrigSizes; 47 48 // AllColors - If index is set, it's a spill slot, i.e. color. 49 // FIXME: This assumes PEI locate spill slot with smaller indices 50 // closest to stack pointer / frame pointer. Therefore, smaller 51 // index == better color. 52 BitVector AllColors; 53 54 // NextColor - Next "color" that's not yet used. 55 int NextColor; 56 57 // UsedColors - "Colors" that have been assigned. 58 BitVector UsedColors; 59 60 // Assignments - Color to intervals mapping. 61 SmallVector<SmallVector<LiveInterval*,4>,16> Assignments; 62 63 public: 64 static char ID; // Pass identification 65 StackSlotColoring() : MachineFunctionPass(&ID), NextColor(-1) {} 66 67 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 68 AU.addRequired<LiveStacks>(); 69 MachineFunctionPass::getAnalysisUsage(AU); 70 } 71 72 virtual bool runOnMachineFunction(MachineFunction &MF); 73 virtual const char* getPassName() const { 74 return "Stack Slot Coloring"; 75 } 76 77 private: 78 bool InitializeSlots(); 79 bool OverlapWithAssignments(LiveInterval *li, int Color) const; 80 int ColorSlot(LiveInterval *li); 81 bool ColorSlots(MachineFunction &MF); 82 }; 83} // end anonymous namespace 84 85char StackSlotColoring::ID = 0; 86 87static RegisterPass<StackSlotColoring> 88X("stack-slot-coloring", "Stack Slot Coloring"); 89 90FunctionPass *llvm::createStackSlotColoringPass() { 91 return new StackSlotColoring(); 92} 93 94namespace { 95 // IntervalSorter - Comparison predicate that sort live intervals by 96 // their weight. 97 struct IntervalSorter { 98 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 99 return LHS->weight > RHS->weight; 100 } 101 }; 102} 103 104/// InitializeSlots - Process all spill stack slot liveintervals and add them 105/// to a sorted (by weight) list. 106bool StackSlotColoring::InitializeSlots() { 107 if (LS->getNumIntervals() < 2) 108 return false; 109 110 int LastFI = MFI->getObjectIndexEnd(); 111 OrigAlignments.resize(LastFI); 112 OrigSizes.resize(LastFI); 113 AllColors.resize(LastFI); 114 UsedColors.resize(LastFI); 115 Assignments.resize(LastFI); 116 117 // Gather all spill slots into a list. 118 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 119 LiveInterval &li = i->second; 120 int FI = li.getStackSlotIndex(); 121 if (MFI->isDeadObjectIndex(FI)) 122 continue; 123 SSIntervals.push_back(&li); 124 OrigAlignments[FI] = MFI->getObjectAlignment(FI); 125 OrigSizes[FI] = MFI->getObjectSize(FI); 126 AllColors.set(FI); 127 } 128 129 // Sort them by weight. 130 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 131 132 // Get first "color". 133 NextColor = AllColors.find_first(); 134 return true; 135} 136 137/// OverlapWithAssignments - Return true if LiveInterval overlaps with any 138/// LiveIntervals that have already been assigned to the specified color. 139bool 140StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 141 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; 142 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 143 LiveInterval *OtherLI = OtherLIs[i]; 144 if (OtherLI->overlaps(*li)) 145 return true; 146 } 147 return false; 148} 149 150/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 151/// 152int StackSlotColoring::ColorSlot(LiveInterval *li) { 153 int Color = -1; 154 bool Share = false; 155 if (!DisableSharing) { 156 // Check if it's possible to reuse any of the used colors. 157 Color = UsedColors.find_first(); 158 while (Color != -1) { 159 if (!OverlapWithAssignments(li, Color)) { 160 Share = true; 161 ++NumEliminated; 162 break; 163 } 164 Color = UsedColors.find_next(Color); 165 } 166 } 167 168 // Assign it to the first available color (assumed to be the best) if it's 169 // not possible to share a used color with other objects. 170 if (!Share) { 171 assert(NextColor != -1 && "No more spill slots?"); 172 Color = NextColor; 173 UsedColors.set(Color); 174 NextColor = AllColors.find_next(NextColor); 175 } 176 177 // Record the assignment. 178 Assignments[Color].push_back(li); 179 int FI = li->getStackSlotIndex(); 180 DOUT << "Assigning fi #" << FI << " to fi #" << Color << "\n"; 181 182 // Change size and alignment of the allocated slot. If there are multiple 183 // objects sharing the same slot, then make sure the size and alignment 184 // are large enough for all. 185 unsigned Align = OrigAlignments[FI]; 186 if (!Share || Align > MFI->getObjectAlignment(Color)) 187 MFI->setObjectAlignment(Color, Align); 188 int64_t Size = OrigSizes[FI]; 189 if (!Share || Size > MFI->getObjectSize(Color)) 190 MFI->setObjectSize(Color, Size); 191 return Color; 192} 193 194/// Colorslots - Color all spill stack slots and rewrite all frameindex machine 195/// operands in the function. 196bool StackSlotColoring::ColorSlots(MachineFunction &MF) { 197 unsigned NumObjs = MFI->getObjectIndexEnd(); 198 std::vector<int> SlotMapping(NumObjs, -1); 199 200 bool Changed = false; 201 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 202 LiveInterval *li = SSIntervals[i]; 203 int SS = li->getStackSlotIndex(); 204 int NewSS = ColorSlot(li); 205 SlotMapping[SS] = NewSS; 206 Changed |= (SS != NewSS); 207 } 208 209 if (!Changed) 210 return false; 211 212 // Rewrite all MO_FrameIndex operands. 213 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 214 for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); 215 MBB != E; ++MBB) { 216 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 217 MII != EE; ++MII) { 218 MachineInstr &MI = *MII; 219 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 220 MachineOperand &MO = MI.getOperand(i); 221 if (!MO.isFrameIndex()) 222 continue; 223 int FI = MO.getIndex(); 224 if (FI < 0) 225 continue; 226 FI = SlotMapping[FI]; 227 if (FI == -1) 228 continue; 229 MO.setIndex(FI); 230 } 231 } 232 } 233 234 // Delete unused stack slots. 235 while (NextColor != -1) { 236 DOUT << "Removing unused stack object fi #" << NextColor << "\n"; 237 MFI->RemoveStackObject(NextColor); 238 NextColor = AllColors.find_next(NextColor); 239 } 240 241 return true; 242} 243 244bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 245 DOUT << "********** Stack Slot Coloring **********\n"; 246 247 MFI = MF.getFrameInfo(); 248 LS = &getAnalysis<LiveStacks>(); 249 250 bool Changed = false; 251 if (InitializeSlots()) 252 Changed = ColorSlots(MF); 253 254 NextColor = -1; 255 SSIntervals.clear(); 256 OrigAlignments.clear(); 257 OrigSizes.clear(); 258 AllColors.clear(); 259 UsedColors.clear(); 260 for (unsigned i = 0, e = Assignments.size(); i != e; ++i) 261 Assignments[i].clear(); 262 Assignments.clear(); 263 264 return Changed; 265} 266