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