1 //===-- StackColoring.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 pass implements the stack-coloring optimization that looks for 11 // lifetime markers machine instructions (LIFESTART_BEGIN and LIFESTART_END), 12 // which represent the possible lifetime of stack slots. It attempts to 13 // merge disjoint stack slots and reduce the used stack space. 14 // NOTE: This pass is not StackSlotColoring, which optimizes spill slots. 15 // 16 // TODO: In the future we plan to improve stack coloring in the following ways: 17 // 1. Allow merging multiple small slots into a single larger slot at different 18 // offsets. 19 // 2. Merge this pass with StackSlotColoring and allow merging of allocas with 20 // spill slots. 21 // 22 //===----------------------------------------------------------------------===// 23 24 #include "llvm/ADT/BitVector.h" 25 #include "llvm/ADT/DepthFirstIterator.h" 26 #include "llvm/ADT/PostOrderIterator.h" 27 #include "llvm/ADT/SetVector.h" 28 #include "llvm/ADT/SmallPtrSet.h" 29 #include "llvm/ADT/Statistic.h" 30 #include "llvm/Analysis/ValueTracking.h" 31 #include "llvm/CodeGen/LiveInterval.h" 32 #include "llvm/CodeGen/MachineBasicBlock.h" 33 #include "llvm/CodeGen/MachineFrameInfo.h" 34 #include "llvm/CodeGen/MachineFunctionPass.h" 35 #include "llvm/CodeGen/MachineLoopInfo.h" 36 #include "llvm/CodeGen/MachineMemOperand.h" 37 #include "llvm/CodeGen/MachineModuleInfo.h" 38 #include "llvm/CodeGen/MachineRegisterInfo.h" 39 #include "llvm/CodeGen/Passes.h" 40 #include "llvm/CodeGen/PseudoSourceValue.h" 41 #include "llvm/CodeGen/SlotIndexes.h" 42 #include "llvm/CodeGen/StackProtector.h" 43 #include "llvm/CodeGen/WinEHFuncInfo.h" 44 #include "llvm/IR/DebugInfo.h" 45 #include "llvm/IR/Function.h" 46 #include "llvm/IR/Instructions.h" 47 #include "llvm/IR/IntrinsicInst.h" 48 #include "llvm/IR/Module.h" 49 #include "llvm/Support/CommandLine.h" 50 #include "llvm/Support/Debug.h" 51 #include "llvm/Support/raw_ostream.h" 52 #include "llvm/Target/TargetInstrInfo.h" 53 #include "llvm/Target/TargetRegisterInfo.h" 54 55 using namespace llvm; 56 57 #define DEBUG_TYPE "stackcoloring" 58 59 static cl::opt<bool> 60 DisableColoring("no-stack-coloring", 61 cl::init(false), cl::Hidden, 62 cl::desc("Disable stack coloring")); 63 64 /// The user may write code that uses allocas outside of the declared lifetime 65 /// zone. This can happen when the user returns a reference to a local 66 /// data-structure. We can detect these cases and decide not to optimize the 67 /// code. If this flag is enabled, we try to save the user. This option 68 /// is treated as overriding LifetimeStartOnFirstUse below. 69 static cl::opt<bool> 70 ProtectFromEscapedAllocas("protect-from-escaped-allocas", 71 cl::init(false), cl::Hidden, 72 cl::desc("Do not optimize lifetime zones that " 73 "are broken")); 74 75 /// Enable enhanced dataflow scheme for lifetime analysis (treat first 76 /// use of stack slot as start of slot lifetime, as opposed to looking 77 /// for LIFETIME_START marker). See "Implementation notes" below for 78 /// more info. 79 static cl::opt<bool> 80 LifetimeStartOnFirstUse("stackcoloring-lifetime-start-on-first-use", 81 cl::init(true), cl::Hidden, 82 cl::desc("Treat stack lifetimes as starting on first use, not on START marker.")); 83 84 85 STATISTIC(NumMarkerSeen, "Number of lifetime markers found."); 86 STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); 87 STATISTIC(StackSlotMerged, "Number of stack slot merged."); 88 STATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region"); 89 90 // 91 // Implementation Notes: 92 // --------------------- 93 // 94 // Consider the following motivating example: 95 // 96 // int foo() { 97 // char b1[1024], b2[1024]; 98 // if (...) { 99 // char b3[1024]; 100 // <uses of b1, b3>; 101 // return x; 102 // } else { 103 // char b4[1024], b5[1024]; 104 // <uses of b2, b4, b5>; 105 // return y; 106 // } 107 // } 108 // 109 // In the code above, "b3" and "b4" are declared in distinct lexical 110 // scopes, meaning that it is easy to prove that they can share the 111 // same stack slot. Variables "b1" and "b2" are declared in the same 112 // scope, meaning that from a lexical point of view, their lifetimes 113 // overlap. From a control flow pointer of view, however, the two 114 // variables are accessed in disjoint regions of the CFG, thus it 115 // should be possible for them to share the same stack slot. An ideal 116 // stack allocation for the function above would look like: 117 // 118 // slot 0: b1, b2 119 // slot 1: b3, b4 120 // slot 2: b5 121 // 122 // Achieving this allocation is tricky, however, due to the way 123 // lifetime markers are inserted. Here is a simplified view of the 124 // control flow graph for the code above: 125 // 126 // +------ block 0 -------+ 127 // 0| LIFETIME_START b1, b2 | 128 // 1| <test 'if' condition> | 129 // +-----------------------+ 130 // ./ \. 131 // +------ block 1 -------+ +------ block 2 -------+ 132 // 2| LIFETIME_START b3 | 5| LIFETIME_START b4, b5 | 133 // 3| <uses of b1, b3> | 6| <uses of b2, b4, b5> | 134 // 4| LIFETIME_END b3 | 7| LIFETIME_END b4, b5 | 135 // +-----------------------+ +-----------------------+ 136 // \. /. 137 // +------ block 3 -------+ 138 // 8| <cleanupcode> | 139 // 9| LIFETIME_END b1, b2 | 140 // 10| return | 141 // +-----------------------+ 142 // 143 // If we create live intervals for the variables above strictly based 144 // on the lifetime markers, we'll get the set of intervals on the 145 // left. If we ignore the lifetime start markers and instead treat a 146 // variable's lifetime as beginning with the first reference to the 147 // var, then we get the intervals on the right. 148 // 149 // LIFETIME_START First Use 150 // b1: [0,9] [3,4] [8,9] 151 // b2: [0,9] [6,9] 152 // b3: [2,4] [3,4] 153 // b4: [5,7] [6,7] 154 // b5: [5,7] [6,7] 155 // 156 // For the intervals on the left, the best we can do is overlap two 157 // variables (b3 and b4, for example); this gives us a stack size of 158 // 4*1024 bytes, not ideal. When treating first-use as the start of a 159 // lifetime, we can additionally overlap b1 and b5, giving us a 3*1024 160 // byte stack (better). 161 // 162 // Relying entirely on first-use of stack slots is problematic, 163 // however, due to the fact that optimizations can sometimes migrate 164 // uses of a variable outside of its lifetime start/end region. Here 165 // is an example: 166 // 167 // int bar() { 168 // char b1[1024], b2[1024]; 169 // if (...) { 170 // <uses of b2> 171 // return y; 172 // } else { 173 // <uses of b1> 174 // while (...) { 175 // char b3[1024]; 176 // <uses of b3> 177 // } 178 // } 179 // } 180 // 181 // Before optimization, the control flow graph for the code above 182 // might look like the following: 183 // 184 // +------ block 0 -------+ 185 // 0| LIFETIME_START b1, b2 | 186 // 1| <test 'if' condition> | 187 // +-----------------------+ 188 // ./ \. 189 // +------ block 1 -------+ +------- block 2 -------+ 190 // 2| <uses of b2> | 3| <uses of b1> | 191 // +-----------------------+ +-----------------------+ 192 // | | 193 // | +------- block 3 -------+ <-\. 194 // | 4| <while condition> | | 195 // | +-----------------------+ | 196 // | / | | 197 // | / +------- block 4 -------+ 198 // \ / 5| LIFETIME_START b3 | | 199 // \ / 6| <uses of b3> | | 200 // \ / 7| LIFETIME_END b3 | | 201 // \ | +------------------------+ | 202 // \ | \ / 203 // +------ block 5 -----+ \--------------- 204 // 8| <cleanupcode> | 205 // 9| LIFETIME_END b1, b2 | 206 // 10| return | 207 // +---------------------+ 208 // 209 // During optimization, however, it can happen that an instruction 210 // computing an address in "b3" (for example, a loop-invariant GEP) is 211 // hoisted up out of the loop from block 4 to block 2. [Note that 212 // this is not an actual load from the stack, only an instruction that 213 // computes the address to be loaded]. If this happens, there is now a 214 // path leading from the first use of b3 to the return instruction 215 // that does not encounter the b3 LIFETIME_END, hence b3's lifetime is 216 // now larger than if we were computing live intervals strictly based 217 // on lifetime markers. In the example above, this lengthened lifetime 218 // would mean that it would appear illegal to overlap b3 with b2. 219 // 220 // To deal with this such cases, the code in ::collectMarkers() below 221 // tries to identify "degenerate" slots -- those slots where on a single 222 // forward pass through the CFG we encounter a first reference to slot 223 // K before we hit the slot K lifetime start marker. For such slots, 224 // we fall back on using the lifetime start marker as the beginning of 225 // the variable's lifetime. NB: with this implementation, slots can 226 // appear degenerate in cases where there is unstructured control flow: 227 // 228 // if (q) goto mid; 229 // if (x > 9) { 230 // int b[100]; 231 // memcpy(&b[0], ...); 232 // mid: b[k] = ...; 233 // abc(&b); 234 // } 235 // 236 // If in RPO ordering chosen to walk the CFG we happen to visit the b[k] 237 // before visiting the memcpy block (which will contain the lifetime start 238 // for "b" then it will appear that 'b' has a degenerate lifetime. 239 // 240 241 //===----------------------------------------------------------------------===// 242 // StackColoring Pass 243 //===----------------------------------------------------------------------===// 244 245 namespace { 246 /// StackColoring - A machine pass for merging disjoint stack allocations, 247 /// marked by the LIFETIME_START and LIFETIME_END pseudo instructions. 248 class StackColoring : public MachineFunctionPass { 249 MachineFrameInfo *MFI; 250 MachineFunction *MF; 251 252 /// A class representing liveness information for a single basic block. 253 /// Each bit in the BitVector represents the liveness property 254 /// for a different stack slot. 255 struct BlockLifetimeInfo { 256 /// Which slots BEGINs in each basic block. 257 BitVector Begin; 258 /// Which slots ENDs in each basic block. 259 BitVector End; 260 /// Which slots are marked as LIVE_IN, coming into each basic block. 261 BitVector LiveIn; 262 /// Which slots are marked as LIVE_OUT, coming out of each basic block. 263 BitVector LiveOut; 264 }; 265 266 /// Maps active slots (per bit) for each basic block. 267 typedef DenseMap<const MachineBasicBlock*, BlockLifetimeInfo> LivenessMap; 268 LivenessMap BlockLiveness; 269 270 /// Maps serial numbers to basic blocks. 271 DenseMap<const MachineBasicBlock*, int> BasicBlocks; 272 /// Maps basic blocks to a serial number. 273 SmallVector<const MachineBasicBlock*, 8> BasicBlockNumbering; 274 275 /// Maps liveness intervals for each slot. 276 SmallVector<std::unique_ptr<LiveInterval>, 16> Intervals; 277 /// VNInfo is used for the construction of LiveIntervals. 278 VNInfo::Allocator VNInfoAllocator; 279 /// SlotIndex analysis object. 280 SlotIndexes *Indexes; 281 /// The stack protector object. 282 StackProtector *SP; 283 284 /// The list of lifetime markers found. These markers are to be removed 285 /// once the coloring is done. 286 SmallVector<MachineInstr*, 8> Markers; 287 288 /// Record the FI slots for which we have seen some sort of 289 /// lifetime marker (either start or end). 290 BitVector InterestingSlots; 291 292 /// FI slots that need to be handled conservatively (for these 293 /// slots lifetime-start-on-first-use is disabled). 294 BitVector ConservativeSlots; 295 296 /// Number of iterations taken during data flow analysis. 297 unsigned NumIterations; 298 299 public: 300 static char ID; 301 StackColoring() : MachineFunctionPass(ID) { 302 initializeStackColoringPass(*PassRegistry::getPassRegistry()); 303 } 304 void getAnalysisUsage(AnalysisUsage &AU) const override; 305 bool runOnMachineFunction(MachineFunction &MF) override; 306 307 private: 308 /// Debug. 309 void dump() const; 310 void dumpIntervals() const; 311 void dumpBB(MachineBasicBlock *MBB) const; 312 void dumpBV(const char *tag, const BitVector &BV) const; 313 314 /// Removes all of the lifetime marker instructions from the function. 315 /// \returns true if any markers were removed. 316 bool removeAllMarkers(); 317 318 /// Scan the machine function and find all of the lifetime markers. 319 /// Record the findings in the BEGIN and END vectors. 320 /// \returns the number of markers found. 321 unsigned collectMarkers(unsigned NumSlot); 322 323 /// Perform the dataflow calculation and calculate the lifetime for each of 324 /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and 325 /// LifetimeLIVE_OUT maps that represent which stack slots are live coming 326 /// in and out blocks. 327 void calculateLocalLiveness(); 328 329 /// Returns TRUE if we're using the first-use-begins-lifetime method for 330 /// this slot (if FALSE, then the start marker is treated as start of lifetime). 331 bool applyFirstUse(int Slot) { 332 if (!LifetimeStartOnFirstUse || ProtectFromEscapedAllocas) 333 return false; 334 if (ConservativeSlots.test(Slot)) 335 return false; 336 return true; 337 } 338 339 /// Examines the specified instruction and returns TRUE if the instruction 340 /// represents the start or end of an interesting lifetime. The slot or slots 341 /// starting or ending are added to the vector "slots" and "isStart" is set 342 /// accordingly. 343 /// \returns True if inst contains a lifetime start or end 344 bool isLifetimeStartOrEnd(const MachineInstr &MI, 345 SmallVector<int, 4> &slots, 346 bool &isStart); 347 348 /// Construct the LiveIntervals for the slots. 349 void calculateLiveIntervals(unsigned NumSlots); 350 351 /// Go over the machine function and change instructions which use stack 352 /// slots to use the joint slots. 353 void remapInstructions(DenseMap<int, int> &SlotRemap); 354 355 /// The input program may contain instructions which are not inside lifetime 356 /// markers. This can happen due to a bug in the compiler or due to a bug in 357 /// user code (for example, returning a reference to a local variable). 358 /// This procedure checks all of the instructions in the function and 359 /// invalidates lifetime ranges which do not contain all of the instructions 360 /// which access that frame slot. 361 void removeInvalidSlotRanges(); 362 363 /// Map entries which point to other entries to their destination. 364 /// A->B->C becomes A->C. 365 void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots); 366 367 /// Used in collectMarkers 368 typedef DenseMap<const MachineBasicBlock*, BitVector> BlockBitVecMap; 369 }; 370 } // end anonymous namespace 371 372 char StackColoring::ID = 0; 373 char &llvm::StackColoringID = StackColoring::ID; 374 375 INITIALIZE_PASS_BEGIN(StackColoring, 376 "stack-coloring", "Merge disjoint stack slots", false, false) 377 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 378 INITIALIZE_PASS_DEPENDENCY(StackProtector) 379 INITIALIZE_PASS_END(StackColoring, 380 "stack-coloring", "Merge disjoint stack slots", false, false) 381 382 void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { 383 AU.addRequired<SlotIndexes>(); 384 AU.addRequired<StackProtector>(); 385 MachineFunctionPass::getAnalysisUsage(AU); 386 } 387 388 #ifndef NDEBUG 389 390 LLVM_DUMP_METHOD void StackColoring::dumpBV(const char *tag, 391 const BitVector &BV) const { 392 DEBUG(dbgs() << tag << " : { "); 393 for (unsigned I = 0, E = BV.size(); I != E; ++I) 394 DEBUG(dbgs() << BV.test(I) << " "); 395 DEBUG(dbgs() << "}\n"); 396 } 397 398 LLVM_DUMP_METHOD void StackColoring::dumpBB(MachineBasicBlock *MBB) const { 399 LivenessMap::const_iterator BI = BlockLiveness.find(MBB); 400 assert(BI != BlockLiveness.end() && "Block not found"); 401 const BlockLifetimeInfo &BlockInfo = BI->second; 402 403 dumpBV("BEGIN", BlockInfo.Begin); 404 dumpBV("END", BlockInfo.End); 405 dumpBV("LIVE_IN", BlockInfo.LiveIn); 406 dumpBV("LIVE_OUT", BlockInfo.LiveOut); 407 } 408 409 LLVM_DUMP_METHOD void StackColoring::dump() const { 410 for (MachineBasicBlock *MBB : depth_first(MF)) { 411 DEBUG(dbgs() << "Inspecting block #" << MBB->getNumber() << " [" 412 << MBB->getName() << "]\n"); 413 DEBUG(dumpBB(MBB)); 414 } 415 } 416 417 LLVM_DUMP_METHOD void StackColoring::dumpIntervals() const { 418 for (unsigned I = 0, E = Intervals.size(); I != E; ++I) { 419 DEBUG(dbgs() << "Interval[" << I << "]:\n"); 420 DEBUG(Intervals[I]->dump()); 421 } 422 } 423 424 #endif // not NDEBUG 425 426 static inline int getStartOrEndSlot(const MachineInstr &MI) 427 { 428 assert((MI.getOpcode() == TargetOpcode::LIFETIME_START || 429 MI.getOpcode() == TargetOpcode::LIFETIME_END) && 430 "Expected LIFETIME_START or LIFETIME_END op"); 431 const MachineOperand &MO = MI.getOperand(0); 432 int Slot = MO.getIndex(); 433 if (Slot >= 0) 434 return Slot; 435 return -1; 436 } 437 438 // 439 // At the moment the only way to end a variable lifetime is with 440 // a VARIABLE_LIFETIME op (which can't contain a start). If things 441 // change and the IR allows for a single inst that both begins 442 // and ends lifetime(s), this interface will need to be reworked. 443 // 444 bool StackColoring::isLifetimeStartOrEnd(const MachineInstr &MI, 445 SmallVector<int, 4> &slots, 446 bool &isStart) 447 { 448 if (MI.getOpcode() == TargetOpcode::LIFETIME_START || 449 MI.getOpcode() == TargetOpcode::LIFETIME_END) { 450 int Slot = getStartOrEndSlot(MI); 451 if (Slot < 0) 452 return false; 453 if (!InterestingSlots.test(Slot)) 454 return false; 455 slots.push_back(Slot); 456 if (MI.getOpcode() == TargetOpcode::LIFETIME_END) { 457 isStart = false; 458 return true; 459 } 460 if (! applyFirstUse(Slot)) { 461 isStart = true; 462 return true; 463 } 464 } else if (LifetimeStartOnFirstUse && !ProtectFromEscapedAllocas) { 465 if (! MI.isDebugValue()) { 466 bool found = false; 467 for (const MachineOperand &MO : MI.operands()) { 468 if (!MO.isFI()) 469 continue; 470 int Slot = MO.getIndex(); 471 if (Slot<0) 472 continue; 473 if (InterestingSlots.test(Slot) && applyFirstUse(Slot)) { 474 slots.push_back(Slot); 475 found = true; 476 } 477 } 478 if (found) { 479 isStart = true; 480 return true; 481 } 482 } 483 } 484 return false; 485 } 486 487 unsigned StackColoring::collectMarkers(unsigned NumSlot) 488 { 489 unsigned MarkersFound = 0; 490 BlockBitVecMap SeenStartMap; 491 InterestingSlots.clear(); 492 InterestingSlots.resize(NumSlot); 493 ConservativeSlots.clear(); 494 ConservativeSlots.resize(NumSlot); 495 496 // number of start and end lifetime ops for each slot 497 SmallVector<int, 8> NumStartLifetimes(NumSlot, 0); 498 SmallVector<int, 8> NumEndLifetimes(NumSlot, 0); 499 500 // Step 1: collect markers and populate the "InterestingSlots" 501 // and "ConservativeSlots" sets. 502 for (MachineBasicBlock *MBB : depth_first(MF)) { 503 504 // Compute the set of slots for which we've seen a START marker but have 505 // not yet seen an END marker at this point in the walk (e.g. on entry 506 // to this bb). 507 BitVector BetweenStartEnd; 508 BetweenStartEnd.resize(NumSlot); 509 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 510 PE = MBB->pred_end(); PI != PE; ++PI) { 511 BlockBitVecMap::const_iterator I = SeenStartMap.find(*PI); 512 if (I != SeenStartMap.end()) { 513 BetweenStartEnd |= I->second; 514 } 515 } 516 517 // Walk the instructions in the block to look for start/end ops. 518 for (MachineInstr &MI : *MBB) { 519 if (MI.getOpcode() == TargetOpcode::LIFETIME_START || 520 MI.getOpcode() == TargetOpcode::LIFETIME_END) { 521 int Slot = getStartOrEndSlot(MI); 522 if (Slot < 0) 523 continue; 524 InterestingSlots.set(Slot); 525 if (MI.getOpcode() == TargetOpcode::LIFETIME_START) { 526 BetweenStartEnd.set(Slot); 527 NumStartLifetimes[Slot] += 1; 528 } else { 529 BetweenStartEnd.reset(Slot); 530 NumEndLifetimes[Slot] += 1; 531 } 532 const AllocaInst *Allocation = MFI->getObjectAllocation(Slot); 533 if (Allocation) { 534 DEBUG(dbgs() << "Found a lifetime "); 535 DEBUG(dbgs() << (MI.getOpcode() == TargetOpcode::LIFETIME_START 536 ? "start" 537 : "end")); 538 DEBUG(dbgs() << " marker for slot #" << Slot); 539 DEBUG(dbgs() << " with allocation: " << Allocation->getName() 540 << "\n"); 541 } 542 Markers.push_back(&MI); 543 MarkersFound += 1; 544 } else { 545 for (const MachineOperand &MO : MI.operands()) { 546 if (!MO.isFI()) 547 continue; 548 int Slot = MO.getIndex(); 549 if (Slot < 0) 550 continue; 551 if (! BetweenStartEnd.test(Slot)) { 552 ConservativeSlots.set(Slot); 553 } 554 } 555 } 556 } 557 BitVector &SeenStart = SeenStartMap[MBB]; 558 SeenStart |= BetweenStartEnd; 559 } 560 if (!MarkersFound) { 561 return 0; 562 } 563 564 // PR27903: slots with multiple start or end lifetime ops are not 565 // safe to enable for "lifetime-start-on-first-use". 566 for (unsigned slot = 0; slot < NumSlot; ++slot) 567 if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1) 568 ConservativeSlots.set(slot); 569 DEBUG(dumpBV("Conservative slots", ConservativeSlots)); 570 571 // Step 2: compute begin/end sets for each block 572 573 // NOTE: We use a reverse-post-order iteration to ensure that we obtain a 574 // deterministic numbering, and because we'll need a post-order iteration 575 // later for solving the liveness dataflow problem. 576 for (MachineBasicBlock *MBB : depth_first(MF)) { 577 578 // Assign a serial number to this basic block. 579 BasicBlocks[MBB] = BasicBlockNumbering.size(); 580 BasicBlockNumbering.push_back(MBB); 581 582 // Keep a reference to avoid repeated lookups. 583 BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB]; 584 585 BlockInfo.Begin.resize(NumSlot); 586 BlockInfo.End.resize(NumSlot); 587 588 SmallVector<int, 4> slots; 589 for (MachineInstr &MI : *MBB) { 590 bool isStart = false; 591 slots.clear(); 592 if (isLifetimeStartOrEnd(MI, slots, isStart)) { 593 if (!isStart) { 594 assert(slots.size() == 1 && "unexpected: MI ends multiple slots"); 595 int Slot = slots[0]; 596 if (BlockInfo.Begin.test(Slot)) { 597 BlockInfo.Begin.reset(Slot); 598 } 599 BlockInfo.End.set(Slot); 600 } else { 601 for (auto Slot : slots) { 602 DEBUG(dbgs() << "Found a use of slot #" << Slot); 603 DEBUG(dbgs() << " at BB#" << MBB->getNumber() << " index "); 604 DEBUG(Indexes->getInstructionIndex(MI).print(dbgs())); 605 const AllocaInst *Allocation = MFI->getObjectAllocation(Slot); 606 if (Allocation) { 607 DEBUG(dbgs() << " with allocation: "<< Allocation->getName()); 608 } 609 DEBUG(dbgs() << "\n"); 610 if (BlockInfo.End.test(Slot)) { 611 BlockInfo.End.reset(Slot); 612 } 613 BlockInfo.Begin.set(Slot); 614 } 615 } 616 } 617 } 618 } 619 620 // Update statistics. 621 NumMarkerSeen += MarkersFound; 622 return MarkersFound; 623 } 624 625 void StackColoring::calculateLocalLiveness() 626 { 627 unsigned NumIters = 0; 628 bool changed = true; 629 while (changed) { 630 changed = false; 631 ++NumIters; 632 633 for (const MachineBasicBlock *BB : BasicBlockNumbering) { 634 635 // Use an iterator to avoid repeated lookups. 636 LivenessMap::iterator BI = BlockLiveness.find(BB); 637 assert(BI != BlockLiveness.end() && "Block not found"); 638 BlockLifetimeInfo &BlockInfo = BI->second; 639 640 // Compute LiveIn by unioning together the LiveOut sets of all preds. 641 BitVector LocalLiveIn; 642 for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(), 643 PE = BB->pred_end(); PI != PE; ++PI) { 644 LivenessMap::const_iterator I = BlockLiveness.find(*PI); 645 assert(I != BlockLiveness.end() && "Predecessor not found"); 646 LocalLiveIn |= I->second.LiveOut; 647 } 648 649 // Compute LiveOut by subtracting out lifetimes that end in this 650 // block, then adding in lifetimes that begin in this block. If 651 // we have both BEGIN and END markers in the same basic block 652 // then we know that the BEGIN marker comes after the END, 653 // because we already handle the case where the BEGIN comes 654 // before the END when collecting the markers (and building the 655 // BEGIN/END vectors). 656 BitVector LocalLiveOut = LocalLiveIn; 657 LocalLiveOut.reset(BlockInfo.End); 658 LocalLiveOut |= BlockInfo.Begin; 659 660 // Update block LiveIn set, noting whether it has changed. 661 if (LocalLiveIn.test(BlockInfo.LiveIn)) { 662 changed = true; 663 BlockInfo.LiveIn |= LocalLiveIn; 664 } 665 666 // Update block LiveOut set, noting whether it has changed. 667 if (LocalLiveOut.test(BlockInfo.LiveOut)) { 668 changed = true; 669 BlockInfo.LiveOut |= LocalLiveOut; 670 } 671 } 672 }// while changed. 673 674 NumIterations = NumIters; 675 } 676 677 void StackColoring::calculateLiveIntervals(unsigned NumSlots) { 678 SmallVector<SlotIndex, 16> Starts; 679 SmallVector<SlotIndex, 16> Finishes; 680 681 // For each block, find which slots are active within this block 682 // and update the live intervals. 683 for (const MachineBasicBlock &MBB : *MF) { 684 Starts.clear(); 685 Starts.resize(NumSlots); 686 Finishes.clear(); 687 Finishes.resize(NumSlots); 688 689 // Create the interval for the basic blocks containing lifetime begin/end. 690 for (const MachineInstr &MI : MBB) { 691 692 SmallVector<int, 4> slots; 693 bool IsStart = false; 694 if (!isLifetimeStartOrEnd(MI, slots, IsStart)) 695 continue; 696 SlotIndex ThisIndex = Indexes->getInstructionIndex(MI); 697 for (auto Slot : slots) { 698 if (IsStart) { 699 if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex) 700 Starts[Slot] = ThisIndex; 701 } else { 702 if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex) 703 Finishes[Slot] = ThisIndex; 704 } 705 } 706 } 707 708 // Create the interval of the blocks that we previously found to be 'alive'. 709 BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB]; 710 for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1; 711 pos = MBBLiveness.LiveIn.find_next(pos)) { 712 Starts[pos] = Indexes->getMBBStartIdx(&MBB); 713 } 714 for (int pos = MBBLiveness.LiveOut.find_first(); pos != -1; 715 pos = MBBLiveness.LiveOut.find_next(pos)) { 716 Finishes[pos] = Indexes->getMBBEndIdx(&MBB); 717 } 718 719 for (unsigned i = 0; i < NumSlots; ++i) { 720 // 721 // When LifetimeStartOnFirstUse is turned on, data flow analysis 722 // is forward (from starts to ends), not bidirectional. A 723 // consequence of this is that we can wind up in situations 724 // where Starts[i] is invalid but Finishes[i] is valid and vice 725 // versa. Example: 726 // 727 // LIFETIME_START x 728 // if (...) { 729 // <use of x> 730 // throw ...; 731 // } 732 // LIFETIME_END x 733 // return 2; 734 // 735 // 736 // Here the slot for "x" will not be live into the block 737 // containing the "return 2" (since lifetimes start with first 738 // use, not at the dominating LIFETIME_START marker). 739 // 740 if (Starts[i].isValid() && !Finishes[i].isValid()) { 741 Finishes[i] = Indexes->getMBBEndIdx(&MBB); 742 } 743 if (!Starts[i].isValid()) 744 continue; 745 746 assert(Starts[i] && Finishes[i] && "Invalid interval"); 747 VNInfo *ValNum = Intervals[i]->getValNumInfo(0); 748 SlotIndex S = Starts[i]; 749 SlotIndex F = Finishes[i]; 750 if (S < F) { 751 // We have a single consecutive region. 752 Intervals[i]->addSegment(LiveInterval::Segment(S, F, ValNum)); 753 } else { 754 // We have two non-consecutive regions. This happens when 755 // LIFETIME_START appears after the LIFETIME_END marker. 756 SlotIndex NewStart = Indexes->getMBBStartIdx(&MBB); 757 SlotIndex NewFin = Indexes->getMBBEndIdx(&MBB); 758 Intervals[i]->addSegment(LiveInterval::Segment(NewStart, F, ValNum)); 759 Intervals[i]->addSegment(LiveInterval::Segment(S, NewFin, ValNum)); 760 } 761 } 762 } 763 } 764 765 bool StackColoring::removeAllMarkers() { 766 unsigned Count = 0; 767 for (MachineInstr *MI : Markers) { 768 MI->eraseFromParent(); 769 Count++; 770 } 771 Markers.clear(); 772 773 DEBUG(dbgs()<<"Removed "<<Count<<" markers.\n"); 774 return Count; 775 } 776 777 void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) { 778 unsigned FixedInstr = 0; 779 unsigned FixedMemOp = 0; 780 unsigned FixedDbg = 0; 781 MachineModuleInfo *MMI = &MF->getMMI(); 782 783 // Remap debug information that refers to stack slots. 784 for (auto &VI : MMI->getVariableDbgInfo()) { 785 if (!VI.Var) 786 continue; 787 if (SlotRemap.count(VI.Slot)) { 788 DEBUG(dbgs() << "Remapping debug info for [" 789 << cast<DILocalVariable>(VI.Var)->getName() << "].\n"); 790 VI.Slot = SlotRemap[VI.Slot]; 791 FixedDbg++; 792 } 793 } 794 795 // Keep a list of *allocas* which need to be remapped. 796 DenseMap<const AllocaInst*, const AllocaInst*> Allocas; 797 for (const std::pair<int, int> &SI : SlotRemap) { 798 const AllocaInst *From = MFI->getObjectAllocation(SI.first); 799 const AllocaInst *To = MFI->getObjectAllocation(SI.second); 800 assert(To && From && "Invalid allocation object"); 801 Allocas[From] = To; 802 803 // AA might be used later for instruction scheduling, and we need it to be 804 // able to deduce the correct aliasing releationships between pointers 805 // derived from the alloca being remapped and the target of that remapping. 806 // The only safe way, without directly informing AA about the remapping 807 // somehow, is to directly update the IR to reflect the change being made 808 // here. 809 Instruction *Inst = const_cast<AllocaInst *>(To); 810 if (From->getType() != To->getType()) { 811 BitCastInst *Cast = new BitCastInst(Inst, From->getType()); 812 Cast->insertAfter(Inst); 813 Inst = Cast; 814 } 815 816 // Allow the stack protector to adjust its value map to account for the 817 // upcoming replacement. 818 SP->adjustForColoring(From, To); 819 820 // The new alloca might not be valid in a llvm.dbg.declare for this 821 // variable, so undef out the use to make the verifier happy. 822 AllocaInst *FromAI = const_cast<AllocaInst *>(From); 823 if (FromAI->isUsedByMetadata()) 824 ValueAsMetadata::handleRAUW(FromAI, UndefValue::get(FromAI->getType())); 825 for (auto &Use : FromAI->uses()) { 826 if (BitCastInst *BCI = dyn_cast<BitCastInst>(Use.get())) 827 if (BCI->isUsedByMetadata()) 828 ValueAsMetadata::handleRAUW(BCI, UndefValue::get(BCI->getType())); 829 } 830 831 // Note that this will not replace uses in MMOs (which we'll update below), 832 // or anywhere else (which is why we won't delete the original 833 // instruction). 834 FromAI->replaceAllUsesWith(Inst); 835 } 836 837 // Remap all instructions to the new stack slots. 838 for (MachineBasicBlock &BB : *MF) 839 for (MachineInstr &I : BB) { 840 // Skip lifetime markers. We'll remove them soon. 841 if (I.getOpcode() == TargetOpcode::LIFETIME_START || 842 I.getOpcode() == TargetOpcode::LIFETIME_END) 843 continue; 844 845 // Update the MachineMemOperand to use the new alloca. 846 for (MachineMemOperand *MMO : I.memoperands()) { 847 // FIXME: In order to enable the use of TBAA when using AA in CodeGen, 848 // we'll also need to update the TBAA nodes in MMOs with values 849 // derived from the merged allocas. When doing this, we'll need to use 850 // the same variant of GetUnderlyingObjects that is used by the 851 // instruction scheduler (that can look through ptrtoint/inttoptr 852 // pairs). 853 854 // We've replaced IR-level uses of the remapped allocas, so we only 855 // need to replace direct uses here. 856 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(MMO->getValue()); 857 if (!AI) 858 continue; 859 860 if (!Allocas.count(AI)) 861 continue; 862 863 MMO->setValue(Allocas[AI]); 864 FixedMemOp++; 865 } 866 867 // Update all of the machine instruction operands. 868 for (MachineOperand &MO : I.operands()) { 869 if (!MO.isFI()) 870 continue; 871 int FromSlot = MO.getIndex(); 872 873 // Don't touch arguments. 874 if (FromSlot<0) 875 continue; 876 877 // Only look at mapped slots. 878 if (!SlotRemap.count(FromSlot)) 879 continue; 880 881 // In a debug build, check that the instruction that we are modifying is 882 // inside the expected live range. If the instruction is not inside 883 // the calculated range then it means that the alloca usage moved 884 // outside of the lifetime markers, or that the user has a bug. 885 // NOTE: Alloca address calculations which happen outside the lifetime 886 // zone are are okay, despite the fact that we don't have a good way 887 // for validating all of the usages of the calculation. 888 #ifndef NDEBUG 889 bool TouchesMemory = I.mayLoad() || I.mayStore(); 890 // If we *don't* protect the user from escaped allocas, don't bother 891 // validating the instructions. 892 if (!I.isDebugValue() && TouchesMemory && ProtectFromEscapedAllocas) { 893 SlotIndex Index = Indexes->getInstructionIndex(I); 894 const LiveInterval *Interval = &*Intervals[FromSlot]; 895 assert(Interval->find(Index) != Interval->end() && 896 "Found instruction usage outside of live range."); 897 } 898 #endif 899 900 // Fix the machine instructions. 901 int ToSlot = SlotRemap[FromSlot]; 902 MO.setIndex(ToSlot); 903 FixedInstr++; 904 } 905 } 906 907 // Update the location of C++ catch objects for the MSVC personality routine. 908 if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo()) 909 for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap) 910 for (WinEHHandlerType &H : TBME.HandlerArray) 911 if (H.CatchObj.FrameIndex != INT_MAX && 912 SlotRemap.count(H.CatchObj.FrameIndex)) 913 H.CatchObj.FrameIndex = SlotRemap[H.CatchObj.FrameIndex]; 914 915 DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n"); 916 DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n"); 917 DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n"); 918 } 919 920 void StackColoring::removeInvalidSlotRanges() { 921 for (MachineBasicBlock &BB : *MF) 922 for (MachineInstr &I : BB) { 923 if (I.getOpcode() == TargetOpcode::LIFETIME_START || 924 I.getOpcode() == TargetOpcode::LIFETIME_END || I.isDebugValue()) 925 continue; 926 927 // Some intervals are suspicious! In some cases we find address 928 // calculations outside of the lifetime zone, but not actual memory 929 // read or write. Memory accesses outside of the lifetime zone are a clear 930 // violation, but address calculations are okay. This can happen when 931 // GEPs are hoisted outside of the lifetime zone. 932 // So, in here we only check instructions which can read or write memory. 933 if (!I.mayLoad() && !I.mayStore()) 934 continue; 935 936 // Check all of the machine operands. 937 for (const MachineOperand &MO : I.operands()) { 938 if (!MO.isFI()) 939 continue; 940 941 int Slot = MO.getIndex(); 942 943 if (Slot<0) 944 continue; 945 946 if (Intervals[Slot]->empty()) 947 continue; 948 949 // Check that the used slot is inside the calculated lifetime range. 950 // If it is not, warn about it and invalidate the range. 951 LiveInterval *Interval = &*Intervals[Slot]; 952 SlotIndex Index = Indexes->getInstructionIndex(I); 953 if (Interval->find(Index) == Interval->end()) { 954 Interval->clear(); 955 DEBUG(dbgs()<<"Invalidating range #"<<Slot<<"\n"); 956 EscapedAllocas++; 957 } 958 } 959 } 960 } 961 962 void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap, 963 unsigned NumSlots) { 964 // Expunge slot remap map. 965 for (unsigned i=0; i < NumSlots; ++i) { 966 // If we are remapping i 967 if (SlotRemap.count(i)) { 968 int Target = SlotRemap[i]; 969 // As long as our target is mapped to something else, follow it. 970 while (SlotRemap.count(Target)) { 971 Target = SlotRemap[Target]; 972 SlotRemap[i] = Target; 973 } 974 } 975 } 976 } 977 978 bool StackColoring::runOnMachineFunction(MachineFunction &Func) { 979 DEBUG(dbgs() << "********** Stack Coloring **********\n" 980 << "********** Function: " 981 << ((const Value*)Func.getFunction())->getName() << '\n'); 982 MF = &Func; 983 MFI = MF->getFrameInfo(); 984 Indexes = &getAnalysis<SlotIndexes>(); 985 SP = &getAnalysis<StackProtector>(); 986 BlockLiveness.clear(); 987 BasicBlocks.clear(); 988 BasicBlockNumbering.clear(); 989 Markers.clear(); 990 Intervals.clear(); 991 VNInfoAllocator.Reset(); 992 993 unsigned NumSlots = MFI->getObjectIndexEnd(); 994 995 // If there are no stack slots then there are no markers to remove. 996 if (!NumSlots) 997 return false; 998 999 SmallVector<int, 8> SortedSlots; 1000 SortedSlots.reserve(NumSlots); 1001 Intervals.reserve(NumSlots); 1002 1003 unsigned NumMarkers = collectMarkers(NumSlots); 1004 1005 unsigned TotalSize = 0; 1006 DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n"); 1007 DEBUG(dbgs()<<"Slot structure:\n"); 1008 1009 for (int i=0; i < MFI->getObjectIndexEnd(); ++i) { 1010 DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n"); 1011 TotalSize += MFI->getObjectSize(i); 1012 } 1013 1014 DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n"); 1015 1016 // Don't continue because there are not enough lifetime markers, or the 1017 // stack is too small, or we are told not to optimize the slots. 1018 if (NumMarkers < 2 || TotalSize < 16 || DisableColoring || 1019 skipFunction(*Func.getFunction())) { 1020 DEBUG(dbgs()<<"Will not try to merge slots.\n"); 1021 return removeAllMarkers(); 1022 } 1023 1024 for (unsigned i=0; i < NumSlots; ++i) { 1025 std::unique_ptr<LiveInterval> LI(new LiveInterval(i, 0)); 1026 LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator); 1027 Intervals.push_back(std::move(LI)); 1028 SortedSlots.push_back(i); 1029 } 1030 1031 // Calculate the liveness of each block. 1032 calculateLocalLiveness(); 1033 DEBUG(dbgs() << "Dataflow iterations: " << NumIterations << "\n"); 1034 DEBUG(dump()); 1035 1036 // Propagate the liveness information. 1037 calculateLiveIntervals(NumSlots); 1038 DEBUG(dumpIntervals()); 1039 1040 // Search for allocas which are used outside of the declared lifetime 1041 // markers. 1042 if (ProtectFromEscapedAllocas) 1043 removeInvalidSlotRanges(); 1044 1045 // Maps old slots to new slots. 1046 DenseMap<int, int> SlotRemap; 1047 unsigned RemovedSlots = 0; 1048 unsigned ReducedSize = 0; 1049 1050 // Do not bother looking at empty intervals. 1051 for (unsigned I = 0; I < NumSlots; ++I) { 1052 if (Intervals[SortedSlots[I]]->empty()) 1053 SortedSlots[I] = -1; 1054 } 1055 1056 // This is a simple greedy algorithm for merging allocas. First, sort the 1057 // slots, placing the largest slots first. Next, perform an n^2 scan and look 1058 // for disjoint slots. When you find disjoint slots, merge the samller one 1059 // into the bigger one and update the live interval. Remove the small alloca 1060 // and continue. 1061 1062 // Sort the slots according to their size. Place unused slots at the end. 1063 // Use stable sort to guarantee deterministic code generation. 1064 std::stable_sort(SortedSlots.begin(), SortedSlots.end(), 1065 [this](int LHS, int RHS) { 1066 // We use -1 to denote a uninteresting slot. Place these slots at the end. 1067 if (LHS == -1) return false; 1068 if (RHS == -1) return true; 1069 // Sort according to size. 1070 return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS); 1071 }); 1072 1073 bool Changed = true; 1074 while (Changed) { 1075 Changed = false; 1076 for (unsigned I = 0; I < NumSlots; ++I) { 1077 if (SortedSlots[I] == -1) 1078 continue; 1079 1080 for (unsigned J=I+1; J < NumSlots; ++J) { 1081 if (SortedSlots[J] == -1) 1082 continue; 1083 1084 int FirstSlot = SortedSlots[I]; 1085 int SecondSlot = SortedSlots[J]; 1086 LiveInterval *First = &*Intervals[FirstSlot]; 1087 LiveInterval *Second = &*Intervals[SecondSlot]; 1088 assert (!First->empty() && !Second->empty() && "Found an empty range"); 1089 1090 // Merge disjoint slots. 1091 if (!First->overlaps(*Second)) { 1092 Changed = true; 1093 First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0)); 1094 SlotRemap[SecondSlot] = FirstSlot; 1095 SortedSlots[J] = -1; 1096 DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<< 1097 SecondSlot<<" together.\n"); 1098 unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot), 1099 MFI->getObjectAlignment(SecondSlot)); 1100 1101 assert(MFI->getObjectSize(FirstSlot) >= 1102 MFI->getObjectSize(SecondSlot) && 1103 "Merging a small object into a larger one"); 1104 1105 RemovedSlots+=1; 1106 ReducedSize += MFI->getObjectSize(SecondSlot); 1107 MFI->setObjectAlignment(FirstSlot, MaxAlignment); 1108 MFI->RemoveStackObject(SecondSlot); 1109 } 1110 } 1111 } 1112 }// While changed. 1113 1114 // Record statistics. 1115 StackSpaceSaved += ReducedSize; 1116 StackSlotMerged += RemovedSlots; 1117 DEBUG(dbgs()<<"Merge "<<RemovedSlots<<" slots. Saved "<< 1118 ReducedSize<<" bytes\n"); 1119 1120 // Scan the entire function and update all machine operands that use frame 1121 // indices to use the remapped frame index. 1122 expungeSlotMap(SlotRemap, NumSlots); 1123 remapInstructions(SlotRemap); 1124 1125 return removeAllMarkers(); 1126 } 1127