StackSlotColoring.cpp revision 26367472a204219b67ba7686f39f91470b6d2c24
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 AU.addPreservedID(MachineLoopInfoID); 70 AU.addPreservedID(MachineDominatorsID); 71 MachineFunctionPass::getAnalysisUsage(AU); 72 } 73 74 virtual bool runOnMachineFunction(MachineFunction &MF); 75 virtual const char* getPassName() const { 76 return "Stack Slot Coloring"; 77 } 78 79 private: 80 bool InitializeSlots(); 81 bool OverlapWithAssignments(LiveInterval *li, int Color) const; 82 int ColorSlot(LiveInterval *li); 83 bool ColorSlots(MachineFunction &MF); 84 }; 85} // end anonymous namespace 86 87char StackSlotColoring::ID = 0; 88 89static RegisterPass<StackSlotColoring> 90X("stack-slot-coloring", "Stack Slot Coloring"); 91 92FunctionPass *llvm::createStackSlotColoringPass() { 93 return new StackSlotColoring(); 94} 95 96namespace { 97 // IntervalSorter - Comparison predicate that sort live intervals by 98 // their weight. 99 struct IntervalSorter { 100 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 101 return LHS->weight > RHS->weight; 102 } 103 }; 104} 105 106/// InitializeSlots - Process all spill stack slot liveintervals and add them 107/// to a sorted (by weight) list. 108bool StackSlotColoring::InitializeSlots() { 109 if (LS->getNumIntervals() < 2) 110 return false; 111 112 int LastFI = MFI->getObjectIndexEnd(); 113 OrigAlignments.resize(LastFI); 114 OrigSizes.resize(LastFI); 115 AllColors.resize(LastFI); 116 UsedColors.resize(LastFI); 117 Assignments.resize(LastFI); 118 119 // Gather all spill slots into a list. 120 for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 121 LiveInterval &li = i->second; 122 int FI = li.getStackSlotIndex(); 123 if (MFI->isDeadObjectIndex(FI)) 124 continue; 125 SSIntervals.push_back(&li); 126 OrigAlignments[FI] = MFI->getObjectAlignment(FI); 127 OrigSizes[FI] = MFI->getObjectSize(FI); 128 AllColors.set(FI); 129 } 130 131 // Sort them by weight. 132 std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 133 134 // Get first "color". 135 NextColor = AllColors.find_first(); 136 return true; 137} 138 139/// OverlapWithAssignments - Return true if LiveInterval overlaps with any 140/// LiveIntervals that have already been assigned to the specified color. 141bool 142StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 143 const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; 144 for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 145 LiveInterval *OtherLI = OtherLIs[i]; 146 if (OtherLI->overlaps(*li)) 147 return true; 148 } 149 return false; 150} 151 152/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 153/// 154int StackSlotColoring::ColorSlot(LiveInterval *li) { 155 int Color = -1; 156 bool Share = false; 157 if (!DisableSharing) { 158 // Check if it's possible to reuse any of the used colors. 159 Color = UsedColors.find_first(); 160 while (Color != -1) { 161 if (!OverlapWithAssignments(li, Color)) { 162 Share = true; 163 ++NumEliminated; 164 break; 165 } 166 Color = UsedColors.find_next(Color); 167 } 168 } 169 170 // Assign it to the first available color (assumed to be the best) if it's 171 // not possible to share a used color with other objects. 172 if (!Share) { 173 assert(NextColor != -1 && "No more spill slots?"); 174 Color = NextColor; 175 UsedColors.set(Color); 176 NextColor = AllColors.find_next(NextColor); 177 } 178 179 // Record the assignment. 180 Assignments[Color].push_back(li); 181 int FI = li->getStackSlotIndex(); 182 DOUT << "Assigning fi#" << FI << " to fi#" << Color << "\n"; 183 184 // Change size and alignment of the allocated slot. If there are multiple 185 // objects sharing the same slot, then make sure the size and alignment 186 // are large enough for all. 187 unsigned Align = OrigAlignments[FI]; 188 if (!Share || Align > MFI->getObjectAlignment(Color)) 189 MFI->setObjectAlignment(Color, Align); 190 int64_t Size = OrigSizes[FI]; 191 if (!Share || Size > MFI->getObjectSize(Color)) 192 MFI->setObjectSize(Color, Size); 193 return Color; 194} 195 196/// Colorslots - Color all spill stack slots and rewrite all frameindex machine 197/// operands in the function. 198bool StackSlotColoring::ColorSlots(MachineFunction &MF) { 199 unsigned NumObjs = MFI->getObjectIndexEnd(); 200 std::vector<int> SlotMapping(NumObjs, -1); 201 202 bool Changed = false; 203 for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 204 LiveInterval *li = SSIntervals[i]; 205 int SS = li->getStackSlotIndex(); 206 int NewSS = ColorSlot(li); 207 SlotMapping[SS] = NewSS; 208 Changed |= (SS != NewSS); 209 } 210 211 if (!Changed) 212 return false; 213 214 // Rewrite all MO_FrameIndex operands. 215 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 216 for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); 217 MBB != E; ++MBB) { 218 for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 219 MII != EE; ++MII) { 220 MachineInstr &MI = *MII; 221 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 222 MachineOperand &MO = MI.getOperand(i); 223 if (!MO.isFI()) 224 continue; 225 int FI = MO.getIndex(); 226 if (FI < 0) 227 continue; 228 FI = SlotMapping[FI]; 229 if (FI == -1) 230 continue; 231 MO.setIndex(FI); 232 } 233 } 234 } 235 236 // Delete unused stack slots. 237 while (NextColor != -1) { 238 DOUT << "Removing unused stack object fi#" << NextColor << "\n"; 239 MFI->RemoveStackObject(NextColor); 240 NextColor = AllColors.find_next(NextColor); 241 } 242 243 return true; 244} 245 246bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 247 DOUT << "********** Stack Slot Coloring **********\n"; 248 249 MFI = MF.getFrameInfo(); 250 LS = &getAnalysis<LiveStacks>(); 251 252 bool Changed = false; 253 if (InitializeSlots()) 254 Changed = ColorSlots(MF); 255 256 NextColor = -1; 257 SSIntervals.clear(); 258 OrigAlignments.clear(); 259 OrigSizes.clear(); 260 AllColors.clear(); 261 UsedColors.clear(); 262 for (unsigned i = 0, e = Assignments.size(); i != e; ++i) 263 Assignments[i].clear(); 264 Assignments.clear(); 265 266 return Changed; 267} 268