| OLD | NEW |
|---|
| (Empty) |
| 1 //===-- AllocaManager.cpp -------------------------------------------------===// | |
| 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 defines the AllocaManager class. | |
| 11 // | |
| 12 // The AllocaManager computes a frame layout, assigning every static alloca an | |
| 13 // offset. It does alloca liveness analysis in order to reuse stack memory, | |
| 14 // using lifetime intrinsics. | |
| 15 // | |
| 16 //===----------------------------------------------------------------------===// | |
| 17 | |
| 18 #define DEBUG_TYPE "allocamanager" | |
| 19 #include "AllocaManager.h" | |
| 20 #include "llvm/ADT/STLExtras.h" | |
| 21 #include "llvm/IR/DataLayout.h" | |
| 22 #include "llvm/IR/IntrinsicInst.h" | |
| 23 #include "llvm/IR/Module.h" | |
| 24 #include "llvm/IR/CFG.h" | |
| 25 #include "llvm/Support/Debug.h" | |
| 26 #include "llvm/Support/raw_ostream.h" | |
| 27 #include "llvm/Support/Timer.h" | |
| 28 #include "llvm/ADT/Statistic.h" | |
| 29 using namespace llvm; | |
| 30 | |
| 31 STATISTIC(NumAllocas, "Number of allocas eliminated"); | |
| 32 | |
| 33 // Return the size of the given alloca. | |
| 34 uint64_t AllocaManager::getSize(const AllocaInst *AI) { | |
| 35 assert(AI->isStaticAlloca()); | |
| 36 return DL->getTypeAllocSize(AI->getAllocatedType()) * | |
| 37 cast<ConstantInt>(AI->getArraySize())->getValue().getZExtValue(); | |
| 38 } | |
| 39 | |
| 40 // Return the alignment of the given alloca. | |
| 41 unsigned AllocaManager::getAlignment(const AllocaInst *AI) { | |
| 42 assert(AI->isStaticAlloca()); | |
| 43 unsigned Alignment = std::max(AI->getAlignment(), | |
| 44 DL->getABITypeAlignment(AI->getAllocatedType()))
; | |
| 45 MaxAlignment = std::max(Alignment, MaxAlignment); | |
| 46 return Alignment; | |
| 47 } | |
| 48 | |
| 49 AllocaManager::AllocaInfo AllocaManager::getInfo(const AllocaInst *AI) { | |
| 50 assert(AI->isStaticAlloca()); | |
| 51 return AllocaInfo(AI, getSize(AI), getAlignment(AI)); | |
| 52 } | |
| 53 | |
| 54 // Given a lifetime_start or lifetime_end intrinsic, determine if it's | |
| 55 // describing a single pointer suitable for our analysis. If so, | |
| 56 // return the pointer, otherwise return NULL. | |
| 57 const Value * | |
| 58 AllocaManager::getPointerFromIntrinsic(const CallInst *CI) { | |
| 59 const IntrinsicInst *II = cast<IntrinsicInst>(CI); | |
| 60 assert(II->getIntrinsicID() == Intrinsic::lifetime_start || | |
| 61 II->getIntrinsicID() == Intrinsic::lifetime_end); | |
| 62 | |
| 63 // Lifetime intrinsics have a size as their first argument and a pointer as | |
| 64 // their second argument. | |
| 65 const Value *Size = II->getArgOperand(0); | |
| 66 const Value *Ptr = II->getArgOperand(1); | |
| 67 | |
| 68 // Check to see if we can convert the size to a host integer. If we can't, | |
| 69 // it's probably not worth worrying about. | |
| 70 const ConstantInt *SizeCon = dyn_cast<ConstantInt>(Size); | |
| 71 if (!SizeCon) return NULL; | |
| 72 const APInt &SizeAP = SizeCon->getValue(); | |
| 73 if (SizeAP.getActiveBits() > 64) return NULL; | |
| 74 uint64_t MarkedSize = SizeAP.getZExtValue(); | |
| 75 | |
| 76 // Test whether the pointer operand is an alloca. This ought to be pretty | |
| 77 // simple, but e.g. PRE can decide to PRE bitcasts and no-op geps and | |
| 78 // split critical edges and insert phis for them, even though it's all | |
| 79 // just no-ops, so we have to dig through phis to see whether all the | |
| 80 // inputs are in fact the same pointer after stripping away casts. | |
| 81 const Value *Result = NULL; | |
| 82 SmallPtrSet<const PHINode *, 8> VisitedPhis; | |
| 83 SmallVector<const Value *, 8> Worklist; | |
| 84 Worklist.push_back(Ptr); | |
| 85 do { | |
| 86 const Value *P = Worklist.pop_back_val()->stripPointerCasts(); | |
| 87 | |
| 88 if (const PHINode *Phi = dyn_cast<PHINode>(P)) { | |
| 89 if (!VisitedPhis.insert(Phi).second) | |
| 90 continue; | |
| 91 for (unsigned i = 0, e = Phi->getNumOperands(); i < e; ++i) | |
| 92 Worklist.push_back(Phi->getOperand(i)); | |
| 93 continue; | |
| 94 } | |
| 95 if (const SelectInst *Select = dyn_cast<SelectInst>(P)) { | |
| 96 Worklist.push_back(Select->getTrueValue()); | |
| 97 Worklist.push_back(Select->getFalseValue()); | |
| 98 continue; | |
| 99 } | |
| 100 | |
| 101 if (Result == NULL) | |
| 102 Result = P; | |
| 103 else if (Result != P) | |
| 104 return NULL; | |
| 105 } while (!Worklist.empty()); | |
| 106 | |
| 107 // If it's a static Alloca, make sure the size is suitable. We test this here | |
| 108 // because if this fails, we need to be as conservative as if we don't know | |
| 109 // what the pointer is. | |
| 110 if (const AllocaInst *AI = dyn_cast<AllocaInst>(Result)) { | |
| 111 if (AI->isStaticAlloca() && MarkedSize < getSize(AI)) | |
| 112 return NULL; | |
| 113 } else if (isa<Instruction>(Result)) { | |
| 114 // And if it's any other kind of non-object/argument, we have to be | |
| 115 // similarly conservative, because we may be dealing with an escaped alloca | |
| 116 // that we can't see. | |
| 117 return NULL; | |
| 118 } | |
| 119 | |
| 120 // Yay, it's all just one Value! | |
| 121 return Result; | |
| 122 } | |
| 123 | |
| 124 // Test whether the given value is an alloca which we have a hope of | |
| 125 const AllocaInst *AllocaManager::isFavorableAlloca(const Value *V) { | |
| 126 const AllocaInst *AI = dyn_cast<AllocaInst>(V); | |
| 127 if (!AI) return NULL; | |
| 128 | |
| 129 if (!AI->isStaticAlloca()) return NULL; | |
| 130 | |
| 131 return AI; | |
| 132 } | |
| 133 | |
| 134 int AllocaManager::AllocaSort(const AllocaInfo *li, const AllocaInfo *ri) { | |
| 135 // Sort by alignment to minimize padding. | |
| 136 if (li->getAlignment() > ri->getAlignment()) return -1; | |
| 137 if (li->getAlignment() < ri->getAlignment()) return 1; | |
| 138 | |
| 139 // Ensure a stable sort. We can do this because the pointers are | |
| 140 // pointing into the same array. | |
| 141 if (li > ri) return -1; | |
| 142 if (li < ri) return 1; | |
| 143 | |
| 144 return 0; | |
| 145 } | |
| 146 | |
| 147 // Collect allocas | |
| 148 void AllocaManager::collectMarkedAllocas() { | |
| 149 NamedRegionTimer Timer("Collect Marked Allocas", "AllocaManager", | |
| 150 TimePassesIsEnabled); | |
| 151 | |
| 152 // Weird semantics: If an alloca *ever* appears in a lifetime start or end | |
| 153 // within the same function, its lifetime begins only at the explicit lifetime | |
| 154 // starts and ends only at the explicit lifetime ends and function exit | |
| 155 // points. Otherwise, its lifetime begins in the entry block and it is live | |
| 156 // everywhere. | |
| 157 // | |
| 158 // And so, instead of just walking the entry block to find all the static | |
| 159 // allocas, we walk the whole body to find the intrinsics so we can find the | |
| 160 // set of static allocas referenced in the intrinsics. | |
| 161 for (Function::const_iterator FI = F->begin(), FE = F->end(); | |
| 162 FI != FE; ++FI) { | |
| 163 for (BasicBlock::const_iterator BI = FI->begin(), BE = FI->end(); | |
| 164 BI != BE; ++BI) { | |
| 165 const CallInst *CI = dyn_cast<CallInst>(BI); | |
| 166 if (!CI) continue; | |
| 167 | |
| 168 const Value *Callee = CI->getCalledValue(); | |
| 169 if (Callee == LifetimeStart || Callee == LifetimeEnd) { | |
| 170 if (const Value *Ptr = getPointerFromIntrinsic(CI)) { | |
| 171 if (const AllocaInst *AI = isFavorableAlloca(Ptr)) | |
| 172 Allocas.insert(std::make_pair(AI, 0)); | |
| 173 } else if (isa<Instruction>(CI->getArgOperand(1)->stripPointerCasts()))
{ | |
| 174 // Oh noes, There's a lifetime intrinsics with something that | |
| 175 // doesn't appear to resolve to an alloca. This means that it's | |
| 176 // possible that it may be declaring a lifetime for some escaping | |
| 177 // alloca. Look out! | |
| 178 Allocas.clear(); | |
| 179 assert(AllocasByIndex.empty()); | |
| 180 return; | |
| 181 } | |
| 182 } | |
| 183 } | |
| 184 } | |
| 185 | |
| 186 // All that said, we still want the intrinsics in the order they appear in the | |
| 187 // block, so that we can represent later ones with earlier ones and skip | |
| 188 // worrying about dominance, so run through the entry block and index those | |
| 189 // allocas which we identified above. | |
| 190 AllocasByIndex.reserve(Allocas.size()); | |
| 191 const BasicBlock *EntryBB = &F->getEntryBlock(); | |
| 192 for (BasicBlock::const_iterator BI = EntryBB->begin(), BE = EntryBB->end(); | |
| 193 BI != BE; ++BI) { | |
| 194 const AllocaInst *AI = dyn_cast<AllocaInst>(BI); | |
| 195 if (!AI || !AI->isStaticAlloca()) continue; | |
| 196 | |
| 197 AllocaMap::iterator I = Allocas.find(AI); | |
| 198 if (I != Allocas.end()) { | |
| 199 I->second = AllocasByIndex.size(); | |
| 200 AllocasByIndex.push_back(getInfo(AI)); | |
| 201 } | |
| 202 } | |
| 203 assert(AllocasByIndex.size() == Allocas.size()); | |
| 204 } | |
| 205 | |
| 206 // Calculate the starting point from which inter-block liveness will be | |
| 207 // computed. | |
| 208 void AllocaManager::collectBlocks() { | |
| 209 NamedRegionTimer Timer("Collect Blocks", "AllocaManager", | |
| 210 TimePassesIsEnabled); | |
| 211 | |
| 212 size_t AllocaCount = AllocasByIndex.size(); | |
| 213 | |
| 214 BitVector Seen(AllocaCount); | |
| 215 | |
| 216 for (Function::const_iterator I = F->begin(), E = F->end(); I != E; ++I) { | |
| 217 const BasicBlock *BB = I; | |
| 218 | |
| 219 BlockLifetimeInfo &BLI = BlockLiveness[BB]; | |
| 220 BLI.Start.resize(AllocaCount); | |
| 221 BLI.End.resize(AllocaCount); | |
| 222 | |
| 223 // Track which allocas we've seen. This is used because if a lifetime start | |
| 224 // is the first lifetime marker for an alloca in a block, the alloca is | |
| 225 // live-in. | |
| 226 Seen.reset(); | |
| 227 | |
| 228 // Walk the instructions and compute the Start and End sets. | |
| 229 for (BasicBlock::const_iterator BI = BB->begin(), BE = BB->end(); | |
| 230 BI != BE; ++BI) { | |
| 231 const CallInst *CI = dyn_cast<CallInst>(BI); | |
| 232 if (!CI) continue; | |
| 233 | |
| 234 const Value *Callee = CI->getCalledValue(); | |
| 235 if (Callee == LifetimeStart) { | |
| 236 if (const Value *Ptr = getPointerFromIntrinsic(CI)) { | |
| 237 if (const AllocaInst *AI = isFavorableAlloca(Ptr)) { | |
| 238 AllocaMap::const_iterator MI = Allocas.find(AI); | |
| 239 if (MI != Allocas.end()) { | |
| 240 size_t AllocaIndex = MI->second; | |
| 241 if (!Seen.test(AllocaIndex)) { | |
| 242 BLI.Start.set(AllocaIndex); | |
| 243 } | |
| 244 BLI.End.reset(AllocaIndex); | |
| 245 Seen.set(AllocaIndex); | |
| 246 } | |
| 247 } | |
| 248 } | |
| 249 } else if (Callee == LifetimeEnd) { | |
| 250 if (const Value *Ptr = getPointerFromIntrinsic(CI)) { | |
| 251 if (const AllocaInst *AI = isFavorableAlloca(Ptr)) { | |
| 252 AllocaMap::const_iterator MI = Allocas.find(AI); | |
| 253 if (MI != Allocas.end()) { | |
| 254 size_t AllocaIndex = MI->second; | |
| 255 BLI.End.set(AllocaIndex); | |
| 256 Seen.set(AllocaIndex); | |
| 257 } | |
| 258 } | |
| 259 } | |
| 260 } | |
| 261 } | |
| 262 | |
| 263 // Lifetimes that start in this block and do not end here are live-out. | |
| 264 BLI.LiveOut = BLI.Start; | |
| 265 BLI.LiveOut.reset(BLI.End); | |
| 266 if (BLI.LiveOut.any()) { | |
| 267 for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB); | |
| 268 SI != SE; ++SI) { | |
| 269 InterBlockTopDownWorklist.insert(*SI); | |
| 270 } | |
| 271 } | |
| 272 | |
| 273 // Lifetimes that end in this block and do not start here are live-in. | |
| 274 // TODO: Is this actually true? What are the semantics of a standalone | |
| 275 // lifetime end? See also the code in computeInterBlockLiveness. | |
| 276 BLI.LiveIn = BLI.End; | |
| 277 BLI.LiveIn.reset(BLI.Start); | |
| 278 if (BLI.LiveIn.any()) { | |
| 279 for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB); | |
| 280 PI != PE; ++PI) { | |
| 281 InterBlockBottomUpWorklist.insert(*PI); | |
| 282 } | |
| 283 } | |
| 284 } | |
| 285 } | |
| 286 | |
| 287 // Compute the LiveIn and LiveOut sets for each block in F. | |
| 288 void AllocaManager::computeInterBlockLiveness() { | |
| 289 NamedRegionTimer Timer("Compute inter-block liveness", "AllocaManager", | |
| 290 TimePassesIsEnabled); | |
| 291 | |
| 292 size_t AllocaCount = AllocasByIndex.size(); | |
| 293 | |
| 294 BitVector Temp(AllocaCount); | |
| 295 | |
| 296 // Proporgate liveness backwards. | |
| 297 while (!InterBlockBottomUpWorklist.empty()) { | |
| 298 const BasicBlock *BB = InterBlockBottomUpWorklist.pop_back_val(); | |
| 299 BlockLifetimeInfo &BLI = BlockLiveness[BB]; | |
| 300 | |
| 301 // Compute the new live-out set. | |
| 302 for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB); | |
| 303 SI != SE; ++SI) { | |
| 304 Temp |= BlockLiveness[*SI].LiveIn; | |
| 305 } | |
| 306 | |
| 307 // If it contains new live blocks, prepare to propagate them. | |
| 308 // TODO: As above, what are the semantics of a standalone lifetime end? | |
| 309 Temp.reset(BLI.Start); | |
| 310 if (Temp.test(BLI.LiveIn)) { | |
| 311 BLI.LiveIn |= Temp; | |
| 312 for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB); | |
| 313 PI != PE; ++PI) { | |
| 314 InterBlockBottomUpWorklist.insert(*PI); | |
| 315 } | |
| 316 } | |
| 317 Temp.reset(); | |
| 318 } | |
| 319 | |
| 320 // Proporgate liveness forwards. | |
| 321 while (!InterBlockTopDownWorklist.empty()) { | |
| 322 const BasicBlock *BB = InterBlockTopDownWorklist.pop_back_val(); | |
| 323 BlockLifetimeInfo &BLI = BlockLiveness[BB]; | |
| 324 | |
| 325 // Compute the new live-in set. | |
| 326 for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB); | |
| 327 PI != PE; ++PI) { | |
| 328 Temp |= BlockLiveness[*PI].LiveOut; | |
| 329 } | |
| 330 | |
| 331 // Also record the live-in values. | |
| 332 BLI.LiveIn |= Temp; | |
| 333 | |
| 334 // If it contains new live blocks, prepare to propagate them. | |
| 335 Temp.reset(BLI.End); | |
| 336 if (Temp.test(BLI.LiveOut)) { | |
| 337 BLI.LiveOut |= Temp; | |
| 338 for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB); | |
| 339 SI != SE; ++SI) { | |
| 340 InterBlockTopDownWorklist.insert(*SI); | |
| 341 } | |
| 342 } | |
| 343 Temp.reset(); | |
| 344 } | |
| 345 } | |
| 346 | |
| 347 // Determine overlapping liveranges within blocks. | |
| 348 void AllocaManager::computeIntraBlockLiveness() { | |
| 349 NamedRegionTimer Timer("Compute intra-block liveness", "AllocaManager", | |
| 350 TimePassesIsEnabled); | |
| 351 | |
| 352 size_t AllocaCount = AllocasByIndex.size(); | |
| 353 | |
| 354 BitVector Current(AllocaCount); | |
| 355 | |
| 356 AllocaCompatibility.resize(AllocaCount, BitVector(AllocaCount, true)); | |
| 357 | |
| 358 for (Function::const_iterator I = F->begin(), E = F->end(); I != E; ++I) { | |
| 359 const BasicBlock *BB = I; | |
| 360 const BlockLifetimeInfo &BLI = BlockLiveness[BB]; | |
| 361 | |
| 362 Current = BLI.LiveIn; | |
| 363 | |
| 364 for (int i = Current.find_first(); i >= 0; i = Current.find_next(i)) { | |
| 365 AllocaCompatibility[i].reset(Current); | |
| 366 } | |
| 367 | |
| 368 for (BasicBlock::const_iterator BI = BB->begin(), BE = BB->end(); | |
| 369 BI != BE; ++BI) { | |
| 370 const CallInst *CI = dyn_cast<CallInst>(BI); | |
| 371 if (!CI) continue; | |
| 372 | |
| 373 const Value *Callee = CI->getCalledValue(); | |
| 374 if (Callee == LifetimeStart) { | |
| 375 if (const Value *Ptr = getPointerFromIntrinsic(CI)) { | |
| 376 if (const AllocaInst *AI = isFavorableAlloca(Ptr)) { | |
| 377 size_t AIndex = Allocas[AI]; | |
| 378 // We conflict with everything else that's currently live. | |
| 379 AllocaCompatibility[AIndex].reset(Current); | |
| 380 // Everything else that's currently live conflicts with us. | |
| 381 for (int i = Current.find_first(); i >= 0; i = Current.find_next(i))
{ | |
| 382 AllocaCompatibility[i].reset(AIndex); | |
| 383 } | |
| 384 // We're now live. | |
| 385 Current.set(AIndex); | |
| 386 } | |
| 387 } | |
| 388 } else if (Callee == LifetimeEnd) { | |
| 389 if (const Value *Ptr = getPointerFromIntrinsic(CI)) { | |
| 390 if (const AllocaInst *AI = isFavorableAlloca(Ptr)) { | |
| 391 size_t AIndex = Allocas[AI]; | |
| 392 // We're no longer live. | |
| 393 Current.reset(AIndex); | |
| 394 } | |
| 395 } | |
| 396 } | |
| 397 } | |
| 398 } | |
| 399 } | |
| 400 | |
| 401 // Decide which allocas will represent which other allocas, and if so what their | |
| 402 // size and alignment will need to be. | |
| 403 void AllocaManager::computeRepresentatives() { | |
| 404 NamedRegionTimer Timer("Compute Representatives", "AllocaManager", | |
| 405 TimePassesIsEnabled); | |
| 406 | |
| 407 for (size_t i = 0, e = AllocasByIndex.size(); i != e; ++i) { | |
| 408 // If we've already represented this alloca with another, don't visit it. | |
| 409 if (AllocasByIndex[i].isForwarded()) continue; | |
| 410 if (i > size_t(INT_MAX)) continue; | |
| 411 | |
| 412 // Find compatible allocas. This is a simple greedy algorithm. | |
| 413 for (int j = int(i); ; ) { | |
| 414 assert(j >= int(i)); | |
| 415 j = AllocaCompatibility[i].find_next(j); | |
| 416 assert(j != int(i)); | |
| 417 if (j < 0) break; | |
| 418 if (!AllocaCompatibility[j][i]) continue; | |
| 419 | |
| 420 DEBUG(dbgs() << "Allocas: " | |
| 421 "Representing " | |
| 422 << AllocasByIndex[j].getInst()->getName() << " " | |
| 423 "with " | |
| 424 << AllocasByIndex[i].getInst()->getName() << "\n"); | |
| 425 ++NumAllocas; | |
| 426 | |
| 427 assert(!AllocasByIndex[j].isForwarded()); | |
| 428 | |
| 429 AllocasByIndex[i].mergeSize(AllocasByIndex[j].getSize()); | |
| 430 AllocasByIndex[i].mergeAlignment(AllocasByIndex[j].getAlignment()); | |
| 431 AllocasByIndex[j].forward(i); | |
| 432 | |
| 433 AllocaCompatibility[i] &= AllocaCompatibility[j]; | |
| 434 AllocaCompatibility[j].reset(); | |
| 435 } | |
| 436 } | |
| 437 } | |
| 438 | |
| 439 void AllocaManager::computeFrameOffsets() { | |
| 440 NamedRegionTimer Timer("Compute Frame Offsets", "AllocaManager", | |
| 441 TimePassesIsEnabled); | |
| 442 | |
| 443 // Walk through the entry block and collect all the allocas, including the | |
| 444 // ones with no lifetime markers that we haven't looked at yet. We walk in | |
| 445 // reverse order so that we can set the representative allocas as those that | |
| 446 // dominate the others as we go. | |
| 447 const BasicBlock *EntryBB = &F->getEntryBlock(); | |
| 448 for (BasicBlock::const_iterator BI = EntryBB->begin(), BE = EntryBB->end(); | |
| 449 BI != BE; ++BI) { | |
| 450 const AllocaInst *AI = dyn_cast<AllocaInst>(BI); | |
| 451 if (!AI || !AI->isStaticAlloca()) continue; | |
| 452 | |
| 453 AllocaMap::const_iterator I = Allocas.find(AI); | |
| 454 if (I != Allocas.end()) { | |
| 455 // An alloca with lifetime markers. Emit the record we've crafted for it, | |
| 456 // if we've chosen to keep it as a representative. | |
| 457 const AllocaInfo &Info = AllocasByIndex[I->second]; | |
| 458 if (!Info.isForwarded()) { | |
| 459 SortedAllocas.push_back(Info); | |
| 460 } | |
| 461 } else { | |
| 462 // An alloca with no lifetime markers. | |
| 463 SortedAllocas.push_back(getInfo(AI)); | |
| 464 } | |
| 465 } | |
| 466 | |
| 467 // Sort the allocas to hopefully reduce padding. | |
| 468 array_pod_sort(SortedAllocas.begin(), SortedAllocas.end(), AllocaSort); | |
| 469 | |
| 470 // Assign stack offsets. | |
| 471 uint64_t CurrentOffset = 0; | |
| 472 for (SmallVectorImpl<AllocaInfo>::const_iterator I = SortedAllocas.begin(), | |
| 473 E = SortedAllocas.end(); I != E; ++I) { | |
| 474 const AllocaInfo &Info = *I; | |
| 475 uint64_t NewOffset = RoundUpToAlignment(CurrentOffset, Info.getAlignment()); | |
| 476 | |
| 477 // For backwards compatibility, align every power-of-two multiple alloca to | |
| 478 // its greatest power-of-two factor, up to 8 bytes. In particular, cube2hash | |
| 479 // is known to depend on this. | |
| 480 // TODO: Consider disabling this and making people fix their code. | |
| 481 if (uint64_t Size = Info.getSize()) { | |
| 482 uint64_t P2 = uint64_t(1) << countTrailingZeros(Size); | |
| 483 unsigned CompatAlign = unsigned(std::min(P2, uint64_t(8))); | |
| 484 NewOffset = RoundUpToAlignment(NewOffset, CompatAlign); | |
| 485 } | |
| 486 | |
| 487 const AllocaInst *AI = Info.getInst(); | |
| 488 StaticAllocas[AI] = StaticAllocation(AI, NewOffset); | |
| 489 | |
| 490 CurrentOffset = NewOffset + Info.getSize(); | |
| 491 } | |
| 492 | |
| 493 // Add allocas that were represented by other allocas to the StaticAllocas map | |
| 494 // so that our clients can look them up. | |
| 495 for (unsigned i = 0, e = AllocasByIndex.size(); i != e; ++i) { | |
| 496 const AllocaInfo &Info = AllocasByIndex[i]; | |
| 497 if (!Info.isForwarded()) continue; | |
| 498 size_t j = Info.getForwardedID(); | |
| 499 assert(!AllocasByIndex[j].isForwarded()); | |
| 500 | |
| 501 StaticAllocaMap::const_iterator I = | |
| 502 StaticAllocas.find(AllocasByIndex[j].getInst()); | |
| 503 assert(I != StaticAllocas.end()); | |
| 504 | |
| 505 std::pair<StaticAllocaMap::const_iterator, bool> Pair = | |
| 506 StaticAllocas.insert(std::make_pair(AllocasByIndex[i].getInst(), | |
| 507 I->second)); | |
| 508 assert(Pair.second); (void)Pair; | |
| 509 } | |
| 510 | |
| 511 // Record the final frame size. Keep the stack pointer 16-byte aligned. | |
| 512 FrameSize = CurrentOffset; | |
| 513 FrameSize = RoundUpToAlignment(FrameSize, 16); | |
| 514 | |
| 515 DEBUG(dbgs() << "Allocas: " | |
| 516 "Statically allocated frame size is " << FrameSize << "\n"); | |
| 517 } | |
| 518 | |
| 519 AllocaManager::AllocaManager() : MaxAlignment(0) { | |
| 520 } | |
| 521 | |
| 522 void AllocaManager::analyze(const Function &Func, const DataLayout &Layout, | |
| 523 bool PerformColoring) { | |
| 524 NamedRegionTimer Timer("AllocaManager", TimePassesIsEnabled); | |
| 525 assert(Allocas.empty()); | |
| 526 assert(AllocasByIndex.empty()); | |
| 527 assert(AllocaCompatibility.empty()); | |
| 528 assert(BlockLiveness.empty()); | |
| 529 assert(StaticAllocas.empty()); | |
| 530 assert(SortedAllocas.empty()); | |
| 531 | |
| 532 DL = &Layout; | |
| 533 F = &Func; | |
| 534 | |
| 535 // Get the declarations for the lifetime intrinsics so we can quickly test to | |
| 536 // see if they are used at all, and for use later if they are. | |
| 537 const Module *M = F->getParent(); | |
| 538 LifetimeStart = M->getFunction(Intrinsic::getName(Intrinsic::lifetime_start)); | |
| 539 LifetimeEnd = M->getFunction(Intrinsic::getName(Intrinsic::lifetime_end)); | |
| 540 | |
| 541 // If we are optimizing and the module contains any lifetime intrinsics, run | |
| 542 // the alloca coloring algorithm. | |
| 543 if (PerformColoring && | |
| 544 ((LifetimeStart && !LifetimeStart->use_empty()) || | |
| 545 (LifetimeEnd && !LifetimeEnd->use_empty()))) { | |
| 546 | |
| 547 collectMarkedAllocas(); | |
| 548 | |
| 549 if (!AllocasByIndex.empty()) { | |
| 550 DEBUG(dbgs() << "Allocas: " | |
| 551 << AllocasByIndex.size() << " marked allocas found\n"); | |
| 552 | |
| 553 collectBlocks(); | |
| 554 computeInterBlockLiveness(); | |
| 555 computeIntraBlockLiveness(); | |
| 556 BlockLiveness.clear(); | |
| 557 | |
| 558 computeRepresentatives(); | |
| 559 AllocaCompatibility.clear(); | |
| 560 } | |
| 561 } | |
| 562 | |
| 563 computeFrameOffsets(); | |
| 564 SortedAllocas.clear(); | |
| 565 Allocas.clear(); | |
| 566 AllocasByIndex.clear(); | |
| 567 } | |
| 568 | |
| 569 void AllocaManager::clear() { | |
| 570 StaticAllocas.clear(); | |
| 571 } | |
| 572 | |
| 573 bool | |
| 574 AllocaManager::getFrameOffset(const AllocaInst *AI, uint64_t *Offset) const { | |
| 575 assert(AI->isStaticAlloca()); | |
| 576 StaticAllocaMap::const_iterator I = StaticAllocas.find(AI); | |
| 577 assert(I != StaticAllocas.end()); | |
| 578 *Offset = I->second.Offset; | |
| 579 return AI == I->second.Representative; | |
| 580 } | |
| 581 | |
| 582 const AllocaInst * | |
| 583 AllocaManager::getRepresentative(const AllocaInst *AI) const { | |
| 584 assert(AI->isStaticAlloca()); | |
| 585 StaticAllocaMap::const_iterator I = StaticAllocas.find(AI); | |
| 586 assert(I != StaticAllocas.end()); | |
| 587 return I->second.Representative; | |
| 588 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1692803002:
Remove Emscripten support (Closed)
Base URL: https://chromium.googlesource.com/a/native_client/pnacl-llvm.git@master