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