1 //===- StackColoring.cpp --------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass implements the stack-coloring optimization that looks for 10 // lifetime markers machine instructions (LIFESTART_BEGIN and LIFESTART_END), 11 // which represent the possible lifetime of stack slots. It attempts to 12 // merge disjoint stack slots and reduce the used stack space. 13 // NOTE: This pass is not StackSlotColoring, which optimizes spill slots. 14 // 15 // TODO: In the future we plan to improve stack coloring in the following ways: 16 // 1. Allow merging multiple small slots into a single larger slot at different 17 // offsets. 18 // 2. Merge this pass with StackSlotColoring and allow merging of allocas with 19 // spill slots. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #include "llvm/ADT/BitVector.h" 24 #include "llvm/ADT/DenseMap.h" 25 #include "llvm/ADT/DepthFirstIterator.h" 26 #include "llvm/ADT/SmallPtrSet.h" 27 #include "llvm/ADT/SmallVector.h" 28 #include "llvm/ADT/Statistic.h" 29 #include "llvm/Analysis/ValueTracking.h" 30 #include "llvm/CodeGen/LiveInterval.h" 31 #include "llvm/CodeGen/MachineBasicBlock.h" 32 #include "llvm/CodeGen/MachineFrameInfo.h" 33 #include "llvm/CodeGen/MachineFunction.h" 34 #include "llvm/CodeGen/MachineFunctionPass.h" 35 #include "llvm/CodeGen/MachineInstr.h" 36 #include "llvm/CodeGen/MachineMemOperand.h" 37 #include "llvm/CodeGen/MachineOperand.h" 38 #include "llvm/CodeGen/Passes.h" 39 #include "llvm/CodeGen/SlotIndexes.h" 40 #include "llvm/CodeGen/TargetOpcodes.h" 41 #include "llvm/CodeGen/WinEHFuncInfo.h" 42 #include "llvm/Config/llvm-config.h" 43 #include "llvm/IR/Constants.h" 44 #include "llvm/IR/DebugInfoMetadata.h" 45 #include "llvm/IR/Instructions.h" 46 #include "llvm/IR/Metadata.h" 47 #include "llvm/IR/Use.h" 48 #include "llvm/IR/Value.h" 49 #include "llvm/InitializePasses.h" 50 #include "llvm/Pass.h" 51 #include "llvm/Support/Casting.h" 52 #include "llvm/Support/CommandLine.h" 53 #include "llvm/Support/Compiler.h" 54 #include "llvm/Support/Debug.h" 55 #include "llvm/Support/raw_ostream.h" 56 #include <algorithm> 57 #include <cassert> 58 #include <limits> 59 #include <memory> 60 #include <utility> 61 62 using namespace llvm; 63 64 #define DEBUG_TYPE "stack-coloring" 65 66 static cl::opt<bool> 67 DisableColoring("no-stack-coloring", 68 cl::init(false), cl::Hidden, 69 cl::desc("Disable stack coloring")); 70 71 /// The user may write code that uses allocas outside of the declared lifetime 72 /// zone. This can happen when the user returns a reference to a local 73 /// data-structure. We can detect these cases and decide not to optimize the 74 /// code. If this flag is enabled, we try to save the user. This option 75 /// is treated as overriding LifetimeStartOnFirstUse below. 76 static cl::opt<bool> 77 ProtectFromEscapedAllocas("protect-from-escaped-allocas", 78 cl::init(false), cl::Hidden, 79 cl::desc("Do not optimize lifetime zones that " 80 "are broken")); 81 82 /// Enable enhanced dataflow scheme for lifetime analysis (treat first 83 /// use of stack slot as start of slot lifetime, as opposed to looking 84 /// for LIFETIME_START marker). See "Implementation notes" below for 85 /// more info. 86 static cl::opt<bool> 87 LifetimeStartOnFirstUse("stackcoloring-lifetime-start-on-first-use", 88 cl::init(true), cl::Hidden, 89 cl::desc("Treat stack lifetimes as starting on first use, not on START marker.")); 90 91 92 STATISTIC(NumMarkerSeen, "Number of lifetime markers found."); 93 STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); 94 STATISTIC(StackSlotMerged, "Number of stack slot merged."); 95 STATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region"); 96 97 //===----------------------------------------------------------------------===// 98 // StackColoring Pass 99 //===----------------------------------------------------------------------===// 100 // 101 // Stack Coloring reduces stack usage by merging stack slots when they 102 // can't be used together. For example, consider the following C program: 103 // 104 // void bar(char *, int); 105 // void foo(bool var) { 106 // A: { 107 // char z[4096]; 108 // bar(z, 0); 109 // } 110 // 111 // char *p; 112 // char x[4096]; 113 // char y[4096]; 114 // if (var) { 115 // p = x; 116 // } else { 117 // bar(y, 1); 118 // p = y + 1024; 119 // } 120 // B: 121 // bar(p, 2); 122 // } 123 // 124 // Naively-compiled, this program would use 12k of stack space. However, the 125 // stack slot corresponding to `z` is always destroyed before either of the 126 // stack slots for `x` or `y` are used, and then `x` is only used if `var` 127 // is true, while `y` is only used if `var` is false. So in no time are 2 128 // of the stack slots used together, and therefore we can merge them, 129 // compiling the function using only a single 4k alloca: 130 // 131 // void foo(bool var) { // equivalent 132 // char x[4096]; 133 // char *p; 134 // bar(x, 0); 135 // if (var) { 136 // p = x; 137 // } else { 138 // bar(x, 1); 139 // p = x + 1024; 140 // } 141 // bar(p, 2); 142 // } 143 // 144 // This is an important optimization if we want stack space to be under 145 // control in large functions, both open-coded ones and ones created by 146 // inlining. 147 // 148 // Implementation Notes: 149 // --------------------- 150 // 151 // An important part of the above reasoning is that `z` can't be accessed 152 // while the latter 2 calls to `bar` are running. This is justified because 153 // `z`'s lifetime is over after we exit from block `A:`, so any further 154 // accesses to it would be UB. The way we represent this information 155 // in LLVM is by having frontends delimit blocks with `lifetime.start` 156 // and `lifetime.end` intrinsics. 157 // 158 // The effect of these intrinsics seems to be as follows (maybe I should 159 // specify this in the reference?): 160 // 161 // L1) at start, each stack-slot is marked as *out-of-scope*, unless no 162 // lifetime intrinsic refers to that stack slot, in which case 163 // it is marked as *in-scope*. 164 // L2) on a `lifetime.start`, a stack slot is marked as *in-scope* and 165 // the stack slot is overwritten with `undef`. 166 // L3) on a `lifetime.end`, a stack slot is marked as *out-of-scope*. 167 // L4) on function exit, all stack slots are marked as *out-of-scope*. 168 // L5) `lifetime.end` is a no-op when called on a slot that is already 169 // *out-of-scope*. 170 // L6) memory accesses to *out-of-scope* stack slots are UB. 171 // L7) when a stack-slot is marked as *out-of-scope*, all pointers to it 172 // are invalidated, unless the slot is "degenerate". This is used to 173 // justify not marking slots as in-use until the pointer to them is 174 // used, but feels a bit hacky in the presence of things like LICM. See 175 // the "Degenerate Slots" section for more details. 176 // 177 // Now, let's ground stack coloring on these rules. We'll define a slot 178 // as *in-use* at a (dynamic) point in execution if it either can be 179 // written to at that point, or if it has a live and non-undef content 180 // at that point. 181 // 182 // Obviously, slots that are never *in-use* together can be merged, and 183 // in our example `foo`, the slots for `x`, `y` and `z` are never 184 // in-use together (of course, sometimes slots that *are* in-use together 185 // might still be mergable, but we don't care about that here). 186 // 187 // In this implementation, we successively merge pairs of slots that are 188 // not *in-use* together. We could be smarter - for example, we could merge 189 // a single large slot with 2 small slots, or we could construct the 190 // interference graph and run a "smart" graph coloring algorithm, but with 191 // that aside, how do we find out whether a pair of slots might be *in-use* 192 // together? 193 // 194 // From our rules, we see that *out-of-scope* slots are never *in-use*, 195 // and from (L7) we see that "non-degenerate" slots remain non-*in-use* 196 // until their address is taken. Therefore, we can approximate slot activity 197 // using dataflow. 198 // 199 // A subtle point: naively, we might try to figure out which pairs of 200 // stack-slots interfere by propagating `S in-use` through the CFG for every 201 // stack-slot `S`, and having `S` and `T` interfere if there is a CFG point in 202 // which they are both *in-use*. 203 // 204 // That is sound, but overly conservative in some cases: in our (artificial) 205 // example `foo`, either `x` or `y` might be in use at the label `B:`, but 206 // as `x` is only in use if we came in from the `var` edge and `y` only 207 // if we came from the `!var` edge, they still can't be in use together. 208 // See PR32488 for an important real-life case. 209 // 210 // If we wanted to find all points of interference precisely, we could 211 // propagate `S in-use` and `S&T in-use` predicates through the CFG. That 212 // would be precise, but requires propagating `O(n^2)` dataflow facts. 213 // 214 // However, we aren't interested in the *set* of points of interference 215 // between 2 stack slots, only *whether* there *is* such a point. So we 216 // can rely on a little trick: for `S` and `T` to be in-use together, 217 // one of them needs to become in-use while the other is in-use (or 218 // they might both become in use simultaneously). We can check this 219 // by also keeping track of the points at which a stack slot might *start* 220 // being in-use. 221 // 222 // Exact first use: 223 // ---------------- 224 // 225 // Consider the following motivating example: 226 // 227 // int foo() { 228 // char b1[1024], b2[1024]; 229 // if (...) { 230 // char b3[1024]; 231 // <uses of b1, b3>; 232 // return x; 233 // } else { 234 // char b4[1024], b5[1024]; 235 // <uses of b2, b4, b5>; 236 // return y; 237 // } 238 // } 239 // 240 // In the code above, "b3" and "b4" are declared in distinct lexical 241 // scopes, meaning that it is easy to prove that they can share the 242 // same stack slot. Variables "b1" and "b2" are declared in the same 243 // scope, meaning that from a lexical point of view, their lifetimes 244 // overlap. From a control flow pointer of view, however, the two 245 // variables are accessed in disjoint regions of the CFG, thus it 246 // should be possible for them to share the same stack slot. An ideal 247 // stack allocation for the function above would look like: 248 // 249 // slot 0: b1, b2 250 // slot 1: b3, b4 251 // slot 2: b5 252 // 253 // Achieving this allocation is tricky, however, due to the way 254 // lifetime markers are inserted. Here is a simplified view of the 255 // control flow graph for the code above: 256 // 257 // +------ block 0 -------+ 258 // 0| LIFETIME_START b1, b2 | 259 // 1| <test 'if' condition> | 260 // +-----------------------+ 261 // ./ \. 262 // +------ block 1 -------+ +------ block 2 -------+ 263 // 2| LIFETIME_START b3 | 5| LIFETIME_START b4, b5 | 264 // 3| <uses of b1, b3> | 6| <uses of b2, b4, b5> | 265 // 4| LIFETIME_END b3 | 7| LIFETIME_END b4, b5 | 266 // +-----------------------+ +-----------------------+ 267 // \. /. 268 // +------ block 3 -------+ 269 // 8| <cleanupcode> | 270 // 9| LIFETIME_END b1, b2 | 271 // 10| return | 272 // +-----------------------+ 273 // 274 // If we create live intervals for the variables above strictly based 275 // on the lifetime markers, we'll get the set of intervals on the 276 // left. If we ignore the lifetime start markers and instead treat a 277 // variable's lifetime as beginning with the first reference to the 278 // var, then we get the intervals on the right. 279 // 280 // LIFETIME_START First Use 281 // b1: [0,9] [3,4] [8,9] 282 // b2: [0,9] [6,9] 283 // b3: [2,4] [3,4] 284 // b4: [5,7] [6,7] 285 // b5: [5,7] [6,7] 286 // 287 // For the intervals on the left, the best we can do is overlap two 288 // variables (b3 and b4, for example); this gives us a stack size of 289 // 4*1024 bytes, not ideal. When treating first-use as the start of a 290 // lifetime, we can additionally overlap b1 and b5, giving us a 3*1024 291 // byte stack (better). 292 // 293 // Degenerate Slots: 294 // ----------------- 295 // 296 // Relying entirely on first-use of stack slots is problematic, 297 // however, due to the fact that optimizations can sometimes migrate 298 // uses of a variable outside of its lifetime start/end region. Here 299 // is an example: 300 // 301 // int bar() { 302 // char b1[1024], b2[1024]; 303 // if (...) { 304 // <uses of b2> 305 // return y; 306 // } else { 307 // <uses of b1> 308 // while (...) { 309 // char b3[1024]; 310 // <uses of b3> 311 // } 312 // } 313 // } 314 // 315 // Before optimization, the control flow graph for the code above 316 // might look like the following: 317 // 318 // +------ block 0 -------+ 319 // 0| LIFETIME_START b1, b2 | 320 // 1| <test 'if' condition> | 321 // +-----------------------+ 322 // ./ \. 323 // +------ block 1 -------+ +------- block 2 -------+ 324 // 2| <uses of b2> | 3| <uses of b1> | 325 // +-----------------------+ +-----------------------+ 326 // | | 327 // | +------- block 3 -------+ <-\. 328 // | 4| <while condition> | | 329 // | +-----------------------+ | 330 // | / | | 331 // | / +------- block 4 -------+ 332 // \ / 5| LIFETIME_START b3 | | 333 // \ / 6| <uses of b3> | | 334 // \ / 7| LIFETIME_END b3 | | 335 // \ | +------------------------+ | 336 // \ | \ / 337 // +------ block 5 -----+ \--------------- 338 // 8| <cleanupcode> | 339 // 9| LIFETIME_END b1, b2 | 340 // 10| return | 341 // +---------------------+ 342 // 343 // During optimization, however, it can happen that an instruction 344 // computing an address in "b3" (for example, a loop-invariant GEP) is 345 // hoisted up out of the loop from block 4 to block 2. [Note that 346 // this is not an actual load from the stack, only an instruction that 347 // computes the address to be loaded]. If this happens, there is now a 348 // path leading from the first use of b3 to the return instruction 349 // that does not encounter the b3 LIFETIME_END, hence b3's lifetime is 350 // now larger than if we were computing live intervals strictly based 351 // on lifetime markers. In the example above, this lengthened lifetime 352 // would mean that it would appear illegal to overlap b3 with b2. 353 // 354 // To deal with this such cases, the code in ::collectMarkers() below 355 // tries to identify "degenerate" slots -- those slots where on a single 356 // forward pass through the CFG we encounter a first reference to slot 357 // K before we hit the slot K lifetime start marker. For such slots, 358 // we fall back on using the lifetime start marker as the beginning of 359 // the variable's lifetime. NB: with this implementation, slots can 360 // appear degenerate in cases where there is unstructured control flow: 361 // 362 // if (q) goto mid; 363 // if (x > 9) { 364 // int b[100]; 365 // memcpy(&b[0], ...); 366 // mid: b[k] = ...; 367 // abc(&b); 368 // } 369 // 370 // If in RPO ordering chosen to walk the CFG we happen to visit the b[k] 371 // before visiting the memcpy block (which will contain the lifetime start 372 // for "b" then it will appear that 'b' has a degenerate lifetime. 373 374 namespace { 375 376 /// StackColoring - A machine pass for merging disjoint stack allocations, 377 /// marked by the LIFETIME_START and LIFETIME_END pseudo instructions. 378 class StackColoring : public MachineFunctionPass { 379 MachineFrameInfo *MFI = nullptr; 380 MachineFunction *MF = nullptr; 381 382 /// A class representing liveness information for a single basic block. 383 /// Each bit in the BitVector represents the liveness property 384 /// for a different stack slot. 385 struct BlockLifetimeInfo { 386 /// Which slots BEGINs in each basic block. 387 BitVector Begin; 388 389 /// Which slots ENDs in each basic block. 390 BitVector End; 391 392 /// Which slots are marked as LIVE_IN, coming into each basic block. 393 BitVector LiveIn; 394 395 /// Which slots are marked as LIVE_OUT, coming out of each basic block. 396 BitVector LiveOut; 397 }; 398 399 /// Maps active slots (per bit) for each basic block. 400 using LivenessMap = DenseMap<const MachineBasicBlock *, BlockLifetimeInfo>; 401 LivenessMap BlockLiveness; 402 403 /// Maps serial numbers to basic blocks. 404 DenseMap<const MachineBasicBlock *, int> BasicBlocks; 405 406 /// Maps basic blocks to a serial number. 407 SmallVector<const MachineBasicBlock *, 8> BasicBlockNumbering; 408 409 /// Maps slots to their use interval. Outside of this interval, slots 410 /// values are either dead or `undef` and they will not be written to. 411 SmallVector<std::unique_ptr<LiveInterval>, 16> Intervals; 412 413 /// Maps slots to the points where they can become in-use. 414 SmallVector<SmallVector<SlotIndex, 4>, 16> LiveStarts; 415 416 /// VNInfo is used for the construction of LiveIntervals. 417 VNInfo::Allocator VNInfoAllocator; 418 419 /// SlotIndex analysis object. 420 SlotIndexes *Indexes = nullptr; 421 422 /// The list of lifetime markers found. These markers are to be removed 423 /// once the coloring is done. 424 SmallVector<MachineInstr*, 8> Markers; 425 426 /// Record the FI slots for which we have seen some sort of 427 /// lifetime marker (either start or end). 428 BitVector InterestingSlots; 429 430 /// FI slots that need to be handled conservatively (for these 431 /// slots lifetime-start-on-first-use is disabled). 432 BitVector ConservativeSlots; 433 434 /// Number of iterations taken during data flow analysis. 435 unsigned NumIterations; 436 437 public: 438 static char ID; 439 440 StackColoring() : MachineFunctionPass(ID) { 441 initializeStackColoringPass(*PassRegistry::getPassRegistry()); 442 } 443 444 void getAnalysisUsage(AnalysisUsage &AU) const override; 445 bool runOnMachineFunction(MachineFunction &Func) override; 446 447 private: 448 /// Used in collectMarkers 449 using BlockBitVecMap = DenseMap<const MachineBasicBlock *, BitVector>; 450 451 /// Debug. 452 void dump() const; 453 void dumpIntervals() const; 454 void dumpBB(MachineBasicBlock *MBB) const; 455 void dumpBV(const char *tag, const BitVector &BV) const; 456 457 /// Removes all of the lifetime marker instructions from the function. 458 /// \returns true if any markers were removed. 459 bool removeAllMarkers(); 460 461 /// Scan the machine function and find all of the lifetime markers. 462 /// Record the findings in the BEGIN and END vectors. 463 /// \returns the number of markers found. 464 unsigned collectMarkers(unsigned NumSlot); 465 466 /// Perform the dataflow calculation and calculate the lifetime for each of 467 /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and 468 /// LifetimeLIVE_OUT maps that represent which stack slots are live coming 469 /// in and out blocks. 470 void calculateLocalLiveness(); 471 472 /// Returns TRUE if we're using the first-use-begins-lifetime method for 473 /// this slot (if FALSE, then the start marker is treated as start of lifetime). 474 bool applyFirstUse(int Slot) { 475 if (!LifetimeStartOnFirstUse || ProtectFromEscapedAllocas) 476 return false; 477 if (ConservativeSlots.test(Slot)) 478 return false; 479 return true; 480 } 481 482 /// Examines the specified instruction and returns TRUE if the instruction 483 /// represents the start or end of an interesting lifetime. The slot or slots 484 /// starting or ending are added to the vector "slots" and "isStart" is set 485 /// accordingly. 486 /// \returns True if inst contains a lifetime start or end 487 bool isLifetimeStartOrEnd(const MachineInstr &MI, 488 SmallVector<int, 4> &slots, 489 bool &isStart); 490 491 /// Construct the LiveIntervals for the slots. 492 void calculateLiveIntervals(unsigned NumSlots); 493 494 /// Go over the machine function and change instructions which use stack 495 /// slots to use the joint slots. 496 void remapInstructions(DenseMap<int, int> &SlotRemap); 497 498 /// The input program may contain instructions which are not inside lifetime 499 /// markers. This can happen due to a bug in the compiler or due to a bug in 500 /// user code (for example, returning a reference to a local variable). 501 /// This procedure checks all of the instructions in the function and 502 /// invalidates lifetime ranges which do not contain all of the instructions 503 /// which access that frame slot. 504 void removeInvalidSlotRanges(); 505 506 /// Map entries which point to other entries to their destination. 507 /// A->B->C becomes A->C. 508 void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots); 509 }; 510 511 } // end anonymous namespace 512 513 char StackColoring::ID = 0; 514 515 char &llvm::StackColoringID = StackColoring::ID; 516 517 INITIALIZE_PASS_BEGIN(StackColoring, DEBUG_TYPE, 518 "Merge disjoint stack slots", false, false) 519 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 520 INITIALIZE_PASS_END(StackColoring, DEBUG_TYPE, 521 "Merge disjoint stack slots", false, false) 522 523 void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { 524 AU.addRequired<SlotIndexes>(); 525 MachineFunctionPass::getAnalysisUsage(AU); 526 } 527 528 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 529 LLVM_DUMP_METHOD void StackColoring::dumpBV(const char *tag, 530 const BitVector &BV) const { 531 dbgs() << tag << " : { "; 532 for (unsigned I = 0, E = BV.size(); I != E; ++I) 533 dbgs() << BV.test(I) << " "; 534 dbgs() << "}\n"; 535 } 536 537 LLVM_DUMP_METHOD void StackColoring::dumpBB(MachineBasicBlock *MBB) const { 538 LivenessMap::const_iterator BI = BlockLiveness.find(MBB); 539 assert(BI != BlockLiveness.end() && "Block not found"); 540 const BlockLifetimeInfo &BlockInfo = BI->second; 541 542 dumpBV("BEGIN", BlockInfo.Begin); 543 dumpBV("END", BlockInfo.End); 544 dumpBV("LIVE_IN", BlockInfo.LiveIn); 545 dumpBV("LIVE_OUT", BlockInfo.LiveOut); 546 } 547 548 LLVM_DUMP_METHOD void StackColoring::dump() const { 549 for (MachineBasicBlock *MBB : depth_first(MF)) { 550 dbgs() << "Inspecting block #" << MBB->getNumber() << " [" 551 << MBB->getName() << "]\n"; 552 dumpBB(MBB); 553 } 554 } 555 556 LLVM_DUMP_METHOD void StackColoring::dumpIntervals() const { 557 for (unsigned I = 0, E = Intervals.size(); I != E; ++I) { 558 dbgs() << "Interval[" << I << "]:\n"; 559 Intervals[I]->dump(); 560 } 561 } 562 #endif 563 564 static inline int getStartOrEndSlot(const MachineInstr &MI) 565 { 566 assert((MI.getOpcode() == TargetOpcode::LIFETIME_START || 567 MI.getOpcode() == TargetOpcode::LIFETIME_END) && 568 "Expected LIFETIME_START or LIFETIME_END op"); 569 const MachineOperand &MO = MI.getOperand(0); 570 int Slot = MO.getIndex(); 571 if (Slot >= 0) 572 return Slot; 573 return -1; 574 } 575 576 // At the moment the only way to end a variable lifetime is with 577 // a VARIABLE_LIFETIME op (which can't contain a start). If things 578 // change and the IR allows for a single inst that both begins 579 // and ends lifetime(s), this interface will need to be reworked. 580 bool StackColoring::isLifetimeStartOrEnd(const MachineInstr &MI, 581 SmallVector<int, 4> &slots, 582 bool &isStart) { 583 if (MI.getOpcode() == TargetOpcode::LIFETIME_START || 584 MI.getOpcode() == TargetOpcode::LIFETIME_END) { 585 int Slot = getStartOrEndSlot(MI); 586 if (Slot < 0) 587 return false; 588 if (!InterestingSlots.test(Slot)) 589 return false; 590 slots.push_back(Slot); 591 if (MI.getOpcode() == TargetOpcode::LIFETIME_END) { 592 isStart = false; 593 return true; 594 } 595 if (!applyFirstUse(Slot)) { 596 isStart = true; 597 return true; 598 } 599 } else if (LifetimeStartOnFirstUse && !ProtectFromEscapedAllocas) { 600 if (!MI.isDebugInstr()) { 601 bool found = false; 602 for (const MachineOperand &MO : MI.operands()) { 603 if (!MO.isFI()) 604 continue; 605 int Slot = MO.getIndex(); 606 if (Slot<0) 607 continue; 608 if (InterestingSlots.test(Slot) && applyFirstUse(Slot)) { 609 slots.push_back(Slot); 610 found = true; 611 } 612 } 613 if (found) { 614 isStart = true; 615 return true; 616 } 617 } 618 } 619 return false; 620 } 621 622 unsigned StackColoring::collectMarkers(unsigned NumSlot) { 623 unsigned MarkersFound = 0; 624 BlockBitVecMap SeenStartMap; 625 InterestingSlots.clear(); 626 InterestingSlots.resize(NumSlot); 627 ConservativeSlots.clear(); 628 ConservativeSlots.resize(NumSlot); 629 630 // number of start and end lifetime ops for each slot 631 SmallVector<int, 8> NumStartLifetimes(NumSlot, 0); 632 SmallVector<int, 8> NumEndLifetimes(NumSlot, 0); 633 634 // Step 1: collect markers and populate the "InterestingSlots" 635 // and "ConservativeSlots" sets. 636 for (MachineBasicBlock *MBB : depth_first(MF)) { 637 // Compute the set of slots for which we've seen a START marker but have 638 // not yet seen an END marker at this point in the walk (e.g. on entry 639 // to this bb). 640 BitVector BetweenStartEnd; 641 BetweenStartEnd.resize(NumSlot); 642 for (const MachineBasicBlock *Pred : MBB->predecessors()) { 643 BlockBitVecMap::const_iterator I = SeenStartMap.find(Pred); 644 if (I != SeenStartMap.end()) { 645 BetweenStartEnd |= I->second; 646 } 647 } 648 649 // Walk the instructions in the block to look for start/end ops. 650 for (MachineInstr &MI : *MBB) { 651 if (MI.isDebugInstr()) 652 continue; 653 if (MI.getOpcode() == TargetOpcode::LIFETIME_START || 654 MI.getOpcode() == TargetOpcode::LIFETIME_END) { 655 int Slot = getStartOrEndSlot(MI); 656 if (Slot < 0) 657 continue; 658 InterestingSlots.set(Slot); 659 if (MI.getOpcode() == TargetOpcode::LIFETIME_START) { 660 BetweenStartEnd.set(Slot); 661 NumStartLifetimes[Slot] += 1; 662 } else { 663 BetweenStartEnd.reset(Slot); 664 NumEndLifetimes[Slot] += 1; 665 } 666 const AllocaInst *Allocation = MFI->getObjectAllocation(Slot); 667 if (Allocation) { 668 LLVM_DEBUG(dbgs() << "Found a lifetime "); 669 LLVM_DEBUG(dbgs() << (MI.getOpcode() == TargetOpcode::LIFETIME_START 670 ? "start" 671 : "end")); 672 LLVM_DEBUG(dbgs() << " marker for slot #" << Slot); 673 LLVM_DEBUG(dbgs() 674 << " with allocation: " << Allocation->getName() << "\n"); 675 } 676 Markers.push_back(&MI); 677 MarkersFound += 1; 678 } else { 679 for (const MachineOperand &MO : MI.operands()) { 680 if (!MO.isFI()) 681 continue; 682 int Slot = MO.getIndex(); 683 if (Slot < 0) 684 continue; 685 if (! BetweenStartEnd.test(Slot)) { 686 ConservativeSlots.set(Slot); 687 } 688 } 689 } 690 } 691 BitVector &SeenStart = SeenStartMap[MBB]; 692 SeenStart |= BetweenStartEnd; 693 } 694 if (!MarkersFound) { 695 return 0; 696 } 697 698 // PR27903: slots with multiple start or end lifetime ops are not 699 // safe to enable for "lifetime-start-on-first-use". 700 for (unsigned slot = 0; slot < NumSlot; ++slot) { 701 if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1) 702 ConservativeSlots.set(slot); 703 } 704 705 // The write to the catch object by the personality function is not propely 706 // modeled in IR: It happens before any cleanuppads are executed, even if the 707 // first mention of the catch object is in a catchpad. As such, mark catch 708 // object slots as conservative, so they are excluded from first-use analysis. 709 if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo()) 710 for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap) 711 for (WinEHHandlerType &H : TBME.HandlerArray) 712 if (H.CatchObj.FrameIndex != std::numeric_limits<int>::max() && 713 H.CatchObj.FrameIndex >= 0) 714 ConservativeSlots.set(H.CatchObj.FrameIndex); 715 716 LLVM_DEBUG(dumpBV("Conservative slots", ConservativeSlots)); 717 718 // Step 2: compute begin/end sets for each block 719 720 // NOTE: We use a depth-first iteration to ensure that we obtain a 721 // deterministic numbering. 722 for (MachineBasicBlock *MBB : depth_first(MF)) { 723 // Assign a serial number to this basic block. 724 BasicBlocks[MBB] = BasicBlockNumbering.size(); 725 BasicBlockNumbering.push_back(MBB); 726 727 // Keep a reference to avoid repeated lookups. 728 BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB]; 729 730 BlockInfo.Begin.resize(NumSlot); 731 BlockInfo.End.resize(NumSlot); 732 733 SmallVector<int, 4> slots; 734 for (MachineInstr &MI : *MBB) { 735 bool isStart = false; 736 slots.clear(); 737 if (isLifetimeStartOrEnd(MI, slots, isStart)) { 738 if (!isStart) { 739 assert(slots.size() == 1 && "unexpected: MI ends multiple slots"); 740 int Slot = slots[0]; 741 if (BlockInfo.Begin.test(Slot)) { 742 BlockInfo.Begin.reset(Slot); 743 } 744 BlockInfo.End.set(Slot); 745 } else { 746 for (auto Slot : slots) { 747 LLVM_DEBUG(dbgs() << "Found a use of slot #" << Slot); 748 LLVM_DEBUG(dbgs() 749 << " at " << printMBBReference(*MBB) << " index "); 750 LLVM_DEBUG(Indexes->getInstructionIndex(MI).print(dbgs())); 751 const AllocaInst *Allocation = MFI->getObjectAllocation(Slot); 752 if (Allocation) { 753 LLVM_DEBUG(dbgs() 754 << " with allocation: " << Allocation->getName()); 755 } 756 LLVM_DEBUG(dbgs() << "\n"); 757 if (BlockInfo.End.test(Slot)) { 758 BlockInfo.End.reset(Slot); 759 } 760 BlockInfo.Begin.set(Slot); 761 } 762 } 763 } 764 } 765 } 766 767 // Update statistics. 768 NumMarkerSeen += MarkersFound; 769 return MarkersFound; 770 } 771 772 void StackColoring::calculateLocalLiveness() { 773 unsigned NumIters = 0; 774 bool changed = true; 775 while (changed) { 776 changed = false; 777 ++NumIters; 778 779 for (const MachineBasicBlock *BB : BasicBlockNumbering) { 780 // Use an iterator to avoid repeated lookups. 781 LivenessMap::iterator BI = BlockLiveness.find(BB); 782 assert(BI != BlockLiveness.end() && "Block not found"); 783 BlockLifetimeInfo &BlockInfo = BI->second; 784 785 // Compute LiveIn by unioning together the LiveOut sets of all preds. 786 BitVector LocalLiveIn; 787 for (MachineBasicBlock *Pred : BB->predecessors()) { 788 LivenessMap::const_iterator I = BlockLiveness.find(Pred); 789 // PR37130: transformations prior to stack coloring can 790 // sometimes leave behind statically unreachable blocks; these 791 // can be safely skipped here. 792 if (I != BlockLiveness.end()) 793 LocalLiveIn |= I->second.LiveOut; 794 } 795 796 // Compute LiveOut by subtracting out lifetimes that end in this 797 // block, then adding in lifetimes that begin in this block. If 798 // we have both BEGIN and END markers in the same basic block 799 // then we know that the BEGIN marker comes after the END, 800 // because we already handle the case where the BEGIN comes 801 // before the END when collecting the markers (and building the 802 // BEGIN/END vectors). 803 BitVector LocalLiveOut = LocalLiveIn; 804 LocalLiveOut.reset(BlockInfo.End); 805 LocalLiveOut |= BlockInfo.Begin; 806 807 // Update block LiveIn set, noting whether it has changed. 808 if (LocalLiveIn.test(BlockInfo.LiveIn)) { 809 changed = true; 810 BlockInfo.LiveIn |= LocalLiveIn; 811 } 812 813 // Update block LiveOut set, noting whether it has changed. 814 if (LocalLiveOut.test(BlockInfo.LiveOut)) { 815 changed = true; 816 BlockInfo.LiveOut |= LocalLiveOut; 817 } 818 } 819 } // while changed. 820 821 NumIterations = NumIters; 822 } 823 824 void StackColoring::calculateLiveIntervals(unsigned NumSlots) { 825 SmallVector<SlotIndex, 16> Starts; 826 SmallVector<bool, 16> DefinitelyInUse; 827 828 // For each block, find which slots are active within this block 829 // and update the live intervals. 830 for (const MachineBasicBlock &MBB : *MF) { 831 Starts.clear(); 832 Starts.resize(NumSlots); 833 DefinitelyInUse.clear(); 834 DefinitelyInUse.resize(NumSlots); 835 836 // Start the interval of the slots that we previously found to be 'in-use'. 837 BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB]; 838 for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1; 839 pos = MBBLiveness.LiveIn.find_next(pos)) { 840 Starts[pos] = Indexes->getMBBStartIdx(&MBB); 841 } 842 843 // Create the interval for the basic blocks containing lifetime begin/end. 844 for (const MachineInstr &MI : MBB) { 845 SmallVector<int, 4> slots; 846 bool IsStart = false; 847 if (!isLifetimeStartOrEnd(MI, slots, IsStart)) 848 continue; 849 SlotIndex ThisIndex = Indexes->getInstructionIndex(MI); 850 for (auto Slot : slots) { 851 if (IsStart) { 852 // If a slot is already definitely in use, we don't have to emit 853 // a new start marker because there is already a pre-existing 854 // one. 855 if (!DefinitelyInUse[Slot]) { 856 LiveStarts[Slot].push_back(ThisIndex); 857 DefinitelyInUse[Slot] = true; 858 } 859 if (!Starts[Slot].isValid()) 860 Starts[Slot] = ThisIndex; 861 } else { 862 if (Starts[Slot].isValid()) { 863 VNInfo *VNI = Intervals[Slot]->getValNumInfo(0); 864 Intervals[Slot]->addSegment( 865 LiveInterval::Segment(Starts[Slot], ThisIndex, VNI)); 866 Starts[Slot] = SlotIndex(); // Invalidate the start index 867 DefinitelyInUse[Slot] = false; 868 } 869 } 870 } 871 } 872 873 // Finish up started segments 874 for (unsigned i = 0; i < NumSlots; ++i) { 875 if (!Starts[i].isValid()) 876 continue; 877 878 SlotIndex EndIdx = Indexes->getMBBEndIdx(&MBB); 879 VNInfo *VNI = Intervals[i]->getValNumInfo(0); 880 Intervals[i]->addSegment(LiveInterval::Segment(Starts[i], EndIdx, VNI)); 881 } 882 } 883 } 884 885 bool StackColoring::removeAllMarkers() { 886 unsigned Count = 0; 887 for (MachineInstr *MI : Markers) { 888 MI->eraseFromParent(); 889 Count++; 890 } 891 Markers.clear(); 892 893 LLVM_DEBUG(dbgs() << "Removed " << Count << " markers.\n"); 894 return Count; 895 } 896 897 void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) { 898 unsigned FixedInstr = 0; 899 unsigned FixedMemOp = 0; 900 unsigned FixedDbg = 0; 901 902 // Remap debug information that refers to stack slots. 903 for (auto &VI : MF->getVariableDbgInfo()) { 904 if (!VI.Var || !VI.inStackSlot()) 905 continue; 906 int Slot = VI.getStackSlot(); 907 if (SlotRemap.count(Slot)) { 908 LLVM_DEBUG(dbgs() << "Remapping debug info for [" 909 << cast<DILocalVariable>(VI.Var)->getName() << "].\n"); 910 VI.updateStackSlot(SlotRemap[Slot]); 911 FixedDbg++; 912 } 913 } 914 915 // Keep a list of *allocas* which need to be remapped. 916 DenseMap<const AllocaInst*, const AllocaInst*> Allocas; 917 918 // Keep a list of allocas which has been affected by the remap. 919 SmallPtrSet<const AllocaInst*, 32> MergedAllocas; 920 921 for (const std::pair<int, int> &SI : SlotRemap) { 922 const AllocaInst *From = MFI->getObjectAllocation(SI.first); 923 const AllocaInst *To = MFI->getObjectAllocation(SI.second); 924 assert(To && From && "Invalid allocation object"); 925 Allocas[From] = To; 926 927 // If From is before wo, its possible that there is a use of From between 928 // them. 929 if (From->comesBefore(To)) 930 const_cast<AllocaInst*>(To)->moveBefore(const_cast<AllocaInst*>(From)); 931 932 // AA might be used later for instruction scheduling, and we need it to be 933 // able to deduce the correct aliasing releationships between pointers 934 // derived from the alloca being remapped and the target of that remapping. 935 // The only safe way, without directly informing AA about the remapping 936 // somehow, is to directly update the IR to reflect the change being made 937 // here. 938 Instruction *Inst = const_cast<AllocaInst *>(To); 939 if (From->getType() != To->getType()) { 940 BitCastInst *Cast = new BitCastInst(Inst, From->getType()); 941 Cast->insertAfter(Inst); 942 Inst = Cast; 943 } 944 945 // We keep both slots to maintain AliasAnalysis metadata later. 946 MergedAllocas.insert(From); 947 MergedAllocas.insert(To); 948 949 // Transfer the stack protector layout tag, but make sure that SSPLK_AddrOf 950 // does not overwrite SSPLK_SmallArray or SSPLK_LargeArray, and make sure 951 // that SSPLK_SmallArray does not overwrite SSPLK_LargeArray. 952 MachineFrameInfo::SSPLayoutKind FromKind 953 = MFI->getObjectSSPLayout(SI.first); 954 MachineFrameInfo::SSPLayoutKind ToKind = MFI->getObjectSSPLayout(SI.second); 955 if (FromKind != MachineFrameInfo::SSPLK_None && 956 (ToKind == MachineFrameInfo::SSPLK_None || 957 (ToKind != MachineFrameInfo::SSPLK_LargeArray && 958 FromKind != MachineFrameInfo::SSPLK_AddrOf))) 959 MFI->setObjectSSPLayout(SI.second, FromKind); 960 961 // The new alloca might not be valid in a llvm.dbg.declare for this 962 // variable, so undef out the use to make the verifier happy. 963 AllocaInst *FromAI = const_cast<AllocaInst *>(From); 964 if (FromAI->isUsedByMetadata()) 965 ValueAsMetadata::handleRAUW(FromAI, UndefValue::get(FromAI->getType())); 966 for (auto &Use : FromAI->uses()) { 967 if (BitCastInst *BCI = dyn_cast<BitCastInst>(Use.get())) 968 if (BCI->isUsedByMetadata()) 969 ValueAsMetadata::handleRAUW(BCI, UndefValue::get(BCI->getType())); 970 } 971 972 // Note that this will not replace uses in MMOs (which we'll update below), 973 // or anywhere else (which is why we won't delete the original 974 // instruction). 975 FromAI->replaceAllUsesWith(Inst); 976 } 977 978 // Remap all instructions to the new stack slots. 979 std::vector<std::vector<MachineMemOperand *>> SSRefs( 980 MFI->getObjectIndexEnd()); 981 for (MachineBasicBlock &BB : *MF) 982 for (MachineInstr &I : BB) { 983 // Skip lifetime markers. We'll remove them soon. 984 if (I.getOpcode() == TargetOpcode::LIFETIME_START || 985 I.getOpcode() == TargetOpcode::LIFETIME_END) 986 continue; 987 988 // Update the MachineMemOperand to use the new alloca. 989 for (MachineMemOperand *MMO : I.memoperands()) { 990 // We've replaced IR-level uses of the remapped allocas, so we only 991 // need to replace direct uses here. 992 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(MMO->getValue()); 993 if (!AI) 994 continue; 995 996 if (!Allocas.count(AI)) 997 continue; 998 999 MMO->setValue(Allocas[AI]); 1000 FixedMemOp++; 1001 } 1002 1003 // Update all of the machine instruction operands. 1004 for (MachineOperand &MO : I.operands()) { 1005 if (!MO.isFI()) 1006 continue; 1007 int FromSlot = MO.getIndex(); 1008 1009 // Don't touch arguments. 1010 if (FromSlot<0) 1011 continue; 1012 1013 // Only look at mapped slots. 1014 if (!SlotRemap.count(FromSlot)) 1015 continue; 1016 1017 // In a debug build, check that the instruction that we are modifying is 1018 // inside the expected live range. If the instruction is not inside 1019 // the calculated range then it means that the alloca usage moved 1020 // outside of the lifetime markers, or that the user has a bug. 1021 // NOTE: Alloca address calculations which happen outside the lifetime 1022 // zone are okay, despite the fact that we don't have a good way 1023 // for validating all of the usages of the calculation. 1024 #ifndef NDEBUG 1025 bool TouchesMemory = I.mayLoadOrStore(); 1026 // If we *don't* protect the user from escaped allocas, don't bother 1027 // validating the instructions. 1028 if (!I.isDebugInstr() && TouchesMemory && ProtectFromEscapedAllocas) { 1029 SlotIndex Index = Indexes->getInstructionIndex(I); 1030 const LiveInterval *Interval = &*Intervals[FromSlot]; 1031 assert(Interval->find(Index) != Interval->end() && 1032 "Found instruction usage outside of live range."); 1033 } 1034 #endif 1035 1036 // Fix the machine instructions. 1037 int ToSlot = SlotRemap[FromSlot]; 1038 MO.setIndex(ToSlot); 1039 FixedInstr++; 1040 } 1041 1042 // We adjust AliasAnalysis information for merged stack slots. 1043 SmallVector<MachineMemOperand *, 2> NewMMOs; 1044 bool ReplaceMemOps = false; 1045 for (MachineMemOperand *MMO : I.memoperands()) { 1046 // Collect MachineMemOperands which reference 1047 // FixedStackPseudoSourceValues with old frame indices. 1048 if (const auto *FSV = dyn_cast_or_null<FixedStackPseudoSourceValue>( 1049 MMO->getPseudoValue())) { 1050 int FI = FSV->getFrameIndex(); 1051 auto To = SlotRemap.find(FI); 1052 if (To != SlotRemap.end()) 1053 SSRefs[FI].push_back(MMO); 1054 } 1055 1056 // If this memory location can be a slot remapped here, 1057 // we remove AA information. 1058 bool MayHaveConflictingAAMD = false; 1059 if (MMO->getAAInfo()) { 1060 if (const Value *MMOV = MMO->getValue()) { 1061 SmallVector<Value *, 4> Objs; 1062 getUnderlyingObjectsForCodeGen(MMOV, Objs); 1063 1064 if (Objs.empty()) 1065 MayHaveConflictingAAMD = true; 1066 else 1067 for (Value *V : Objs) { 1068 // If this memory location comes from a known stack slot 1069 // that is not remapped, we continue checking. 1070 // Otherwise, we need to invalidate AA infomation. 1071 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V); 1072 if (AI && MergedAllocas.count(AI)) { 1073 MayHaveConflictingAAMD = true; 1074 break; 1075 } 1076 } 1077 } 1078 } 1079 if (MayHaveConflictingAAMD) { 1080 NewMMOs.push_back(MF->getMachineMemOperand(MMO, AAMDNodes())); 1081 ReplaceMemOps = true; 1082 } else { 1083 NewMMOs.push_back(MMO); 1084 } 1085 } 1086 1087 // If any memory operand is updated, set memory references of 1088 // this instruction. 1089 if (ReplaceMemOps) 1090 I.setMemRefs(*MF, NewMMOs); 1091 } 1092 1093 // Rewrite MachineMemOperands that reference old frame indices. 1094 for (auto E : enumerate(SSRefs)) 1095 if (!E.value().empty()) { 1096 const PseudoSourceValue *NewSV = 1097 MF->getPSVManager().getFixedStack(SlotRemap.find(E.index())->second); 1098 for (MachineMemOperand *Ref : E.value()) 1099 Ref->setValue(NewSV); 1100 } 1101 1102 // Update the location of C++ catch objects for the MSVC personality routine. 1103 if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo()) 1104 for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap) 1105 for (WinEHHandlerType &H : TBME.HandlerArray) 1106 if (H.CatchObj.FrameIndex != std::numeric_limits<int>::max() && 1107 SlotRemap.count(H.CatchObj.FrameIndex)) 1108 H.CatchObj.FrameIndex = SlotRemap[H.CatchObj.FrameIndex]; 1109 1110 LLVM_DEBUG(dbgs() << "Fixed " << FixedMemOp << " machine memory operands.\n"); 1111 LLVM_DEBUG(dbgs() << "Fixed " << FixedDbg << " debug locations.\n"); 1112 LLVM_DEBUG(dbgs() << "Fixed " << FixedInstr << " machine instructions.\n"); 1113 (void) FixedMemOp; 1114 (void) FixedDbg; 1115 (void) FixedInstr; 1116 } 1117 1118 void StackColoring::removeInvalidSlotRanges() { 1119 for (MachineBasicBlock &BB : *MF) 1120 for (MachineInstr &I : BB) { 1121 if (I.getOpcode() == TargetOpcode::LIFETIME_START || 1122 I.getOpcode() == TargetOpcode::LIFETIME_END || I.isDebugInstr()) 1123 continue; 1124 1125 // Some intervals are suspicious! In some cases we find address 1126 // calculations outside of the lifetime zone, but not actual memory 1127 // read or write. Memory accesses outside of the lifetime zone are a clear 1128 // violation, but address calculations are okay. This can happen when 1129 // GEPs are hoisted outside of the lifetime zone. 1130 // So, in here we only check instructions which can read or write memory. 1131 if (!I.mayLoad() && !I.mayStore()) 1132 continue; 1133 1134 // Check all of the machine operands. 1135 for (const MachineOperand &MO : I.operands()) { 1136 if (!MO.isFI()) 1137 continue; 1138 1139 int Slot = MO.getIndex(); 1140 1141 if (Slot<0) 1142 continue; 1143 1144 if (Intervals[Slot]->empty()) 1145 continue; 1146 1147 // Check that the used slot is inside the calculated lifetime range. 1148 // If it is not, warn about it and invalidate the range. 1149 LiveInterval *Interval = &*Intervals[Slot]; 1150 SlotIndex Index = Indexes->getInstructionIndex(I); 1151 if (Interval->find(Index) == Interval->end()) { 1152 Interval->clear(); 1153 LLVM_DEBUG(dbgs() << "Invalidating range #" << Slot << "\n"); 1154 EscapedAllocas++; 1155 } 1156 } 1157 } 1158 } 1159 1160 void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap, 1161 unsigned NumSlots) { 1162 // Expunge slot remap map. 1163 for (unsigned i=0; i < NumSlots; ++i) { 1164 // If we are remapping i 1165 if (SlotRemap.count(i)) { 1166 int Target = SlotRemap[i]; 1167 // As long as our target is mapped to something else, follow it. 1168 while (SlotRemap.count(Target)) { 1169 Target = SlotRemap[Target]; 1170 SlotRemap[i] = Target; 1171 } 1172 } 1173 } 1174 } 1175 1176 bool StackColoring::runOnMachineFunction(MachineFunction &Func) { 1177 LLVM_DEBUG(dbgs() << "********** Stack Coloring **********\n" 1178 << "********** Function: " << Func.getName() << '\n'); 1179 MF = &Func; 1180 MFI = &MF->getFrameInfo(); 1181 Indexes = &getAnalysis<SlotIndexes>(); 1182 BlockLiveness.clear(); 1183 BasicBlocks.clear(); 1184 BasicBlockNumbering.clear(); 1185 Markers.clear(); 1186 Intervals.clear(); 1187 LiveStarts.clear(); 1188 VNInfoAllocator.Reset(); 1189 1190 unsigned NumSlots = MFI->getObjectIndexEnd(); 1191 1192 // If there are no stack slots then there are no markers to remove. 1193 if (!NumSlots) 1194 return false; 1195 1196 SmallVector<int, 8> SortedSlots; 1197 SortedSlots.reserve(NumSlots); 1198 Intervals.reserve(NumSlots); 1199 LiveStarts.resize(NumSlots); 1200 1201 unsigned NumMarkers = collectMarkers(NumSlots); 1202 1203 unsigned TotalSize = 0; 1204 LLVM_DEBUG(dbgs() << "Found " << NumMarkers << " markers and " << NumSlots 1205 << " slots\n"); 1206 LLVM_DEBUG(dbgs() << "Slot structure:\n"); 1207 1208 for (int i=0; i < MFI->getObjectIndexEnd(); ++i) { 1209 LLVM_DEBUG(dbgs() << "Slot #" << i << " - " << MFI->getObjectSize(i) 1210 << " bytes.\n"); 1211 TotalSize += MFI->getObjectSize(i); 1212 } 1213 1214 LLVM_DEBUG(dbgs() << "Total Stack size: " << TotalSize << " bytes\n\n"); 1215 1216 // Don't continue because there are not enough lifetime markers, or the 1217 // stack is too small, or we are told not to optimize the slots. 1218 if (NumMarkers < 2 || TotalSize < 16 || DisableColoring || 1219 skipFunction(Func.getFunction())) { 1220 LLVM_DEBUG(dbgs() << "Will not try to merge slots.\n"); 1221 return removeAllMarkers(); 1222 } 1223 1224 for (unsigned i=0; i < NumSlots; ++i) { 1225 std::unique_ptr<LiveInterval> LI(new LiveInterval(i, 0)); 1226 LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator); 1227 Intervals.push_back(std::move(LI)); 1228 SortedSlots.push_back(i); 1229 } 1230 1231 // Calculate the liveness of each block. 1232 calculateLocalLiveness(); 1233 LLVM_DEBUG(dbgs() << "Dataflow iterations: " << NumIterations << "\n"); 1234 LLVM_DEBUG(dump()); 1235 1236 // Propagate the liveness information. 1237 calculateLiveIntervals(NumSlots); 1238 LLVM_DEBUG(dumpIntervals()); 1239 1240 // Search for allocas which are used outside of the declared lifetime 1241 // markers. 1242 if (ProtectFromEscapedAllocas) 1243 removeInvalidSlotRanges(); 1244 1245 // Maps old slots to new slots. 1246 DenseMap<int, int> SlotRemap; 1247 unsigned RemovedSlots = 0; 1248 unsigned ReducedSize = 0; 1249 1250 // Do not bother looking at empty intervals. 1251 for (unsigned I = 0; I < NumSlots; ++I) { 1252 if (Intervals[SortedSlots[I]]->empty()) 1253 SortedSlots[I] = -1; 1254 } 1255 1256 // This is a simple greedy algorithm for merging allocas. First, sort the 1257 // slots, placing the largest slots first. Next, perform an n^2 scan and look 1258 // for disjoint slots. When you find disjoint slots, merge the smaller one 1259 // into the bigger one and update the live interval. Remove the small alloca 1260 // and continue. 1261 1262 // Sort the slots according to their size. Place unused slots at the end. 1263 // Use stable sort to guarantee deterministic code generation. 1264 llvm::stable_sort(SortedSlots, [this](int LHS, int RHS) { 1265 // We use -1 to denote a uninteresting slot. Place these slots at the end. 1266 if (LHS == -1) 1267 return false; 1268 if (RHS == -1) 1269 return true; 1270 // Sort according to size. 1271 return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS); 1272 }); 1273 1274 for (auto &s : LiveStarts) 1275 llvm::sort(s); 1276 1277 bool Changed = true; 1278 while (Changed) { 1279 Changed = false; 1280 for (unsigned I = 0; I < NumSlots; ++I) { 1281 if (SortedSlots[I] == -1) 1282 continue; 1283 1284 for (unsigned J=I+1; J < NumSlots; ++J) { 1285 if (SortedSlots[J] == -1) 1286 continue; 1287 1288 int FirstSlot = SortedSlots[I]; 1289 int SecondSlot = SortedSlots[J]; 1290 1291 // Objects with different stack IDs cannot be merged. 1292 if (MFI->getStackID(FirstSlot) != MFI->getStackID(SecondSlot)) 1293 continue; 1294 1295 LiveInterval *First = &*Intervals[FirstSlot]; 1296 LiveInterval *Second = &*Intervals[SecondSlot]; 1297 auto &FirstS = LiveStarts[FirstSlot]; 1298 auto &SecondS = LiveStarts[SecondSlot]; 1299 assert(!First->empty() && !Second->empty() && "Found an empty range"); 1300 1301 // Merge disjoint slots. This is a little bit tricky - see the 1302 // Implementation Notes section for an explanation. 1303 if (!First->isLiveAtIndexes(SecondS) && 1304 !Second->isLiveAtIndexes(FirstS)) { 1305 Changed = true; 1306 First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0)); 1307 1308 int OldSize = FirstS.size(); 1309 FirstS.append(SecondS.begin(), SecondS.end()); 1310 auto Mid = FirstS.begin() + OldSize; 1311 std::inplace_merge(FirstS.begin(), Mid, FirstS.end()); 1312 1313 SlotRemap[SecondSlot] = FirstSlot; 1314 SortedSlots[J] = -1; 1315 LLVM_DEBUG(dbgs() << "Merging #" << FirstSlot << " and slots #" 1316 << SecondSlot << " together.\n"); 1317 Align MaxAlignment = std::max(MFI->getObjectAlign(FirstSlot), 1318 MFI->getObjectAlign(SecondSlot)); 1319 1320 assert(MFI->getObjectSize(FirstSlot) >= 1321 MFI->getObjectSize(SecondSlot) && 1322 "Merging a small object into a larger one"); 1323 1324 RemovedSlots+=1; 1325 ReducedSize += MFI->getObjectSize(SecondSlot); 1326 MFI->setObjectAlignment(FirstSlot, MaxAlignment); 1327 MFI->RemoveStackObject(SecondSlot); 1328 } 1329 } 1330 } 1331 }// While changed. 1332 1333 // Record statistics. 1334 StackSpaceSaved += ReducedSize; 1335 StackSlotMerged += RemovedSlots; 1336 LLVM_DEBUG(dbgs() << "Merge " << RemovedSlots << " slots. Saved " 1337 << ReducedSize << " bytes\n"); 1338 1339 // Scan the entire function and update all machine operands that use frame 1340 // indices to use the remapped frame index. 1341 expungeSlotMap(SlotRemap, NumSlots); 1342 remapInstructions(SlotRemap); 1343 1344 return removeAllMarkers(); 1345 } 1346