MemorySSA.cpp revision 335799
1//===- MemorySSA.cpp - Memory SSA Builder ---------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the MemorySSA class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Analysis/MemorySSA.h" 15#include "llvm/ADT/DenseMap.h" 16#include "llvm/ADT/DenseMapInfo.h" 17#include "llvm/ADT/DenseSet.h" 18#include "llvm/ADT/DepthFirstIterator.h" 19#include "llvm/ADT/Hashing.h" 20#include "llvm/ADT/None.h" 21#include "llvm/ADT/Optional.h" 22#include "llvm/ADT/STLExtras.h" 23#include "llvm/ADT/SmallPtrSet.h" 24#include "llvm/ADT/SmallVector.h" 25#include "llvm/ADT/iterator.h" 26#include "llvm/ADT/iterator_range.h" 27#include "llvm/Analysis/AliasAnalysis.h" 28#include "llvm/Analysis/IteratedDominanceFrontier.h" 29#include "llvm/Analysis/MemoryLocation.h" 30#include "llvm/IR/AssemblyAnnotationWriter.h" 31#include "llvm/IR/BasicBlock.h" 32#include "llvm/IR/CallSite.h" 33#include "llvm/IR/Dominators.h" 34#include "llvm/IR/Function.h" 35#include "llvm/IR/Instruction.h" 36#include "llvm/IR/Instructions.h" 37#include "llvm/IR/IntrinsicInst.h" 38#include "llvm/IR/Intrinsics.h" 39#include "llvm/IR/LLVMContext.h" 40#include "llvm/IR/PassManager.h" 41#include "llvm/IR/Use.h" 42#include "llvm/Pass.h" 43#include "llvm/Support/AtomicOrdering.h" 44#include "llvm/Support/Casting.h" 45#include "llvm/Support/CommandLine.h" 46#include "llvm/Support/Compiler.h" 47#include "llvm/Support/Debug.h" 48#include "llvm/Support/ErrorHandling.h" 49#include "llvm/Support/FormattedStream.h" 50#include "llvm/Support/raw_ostream.h" 51#include <algorithm> 52#include <cassert> 53#include <iterator> 54#include <memory> 55#include <utility> 56 57using namespace llvm; 58 59#define DEBUG_TYPE "memoryssa" 60 61INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false, 62 true) 63INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 64INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 65INITIALIZE_PASS_END(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false, 66 true) 67 68INITIALIZE_PASS_BEGIN(MemorySSAPrinterLegacyPass, "print-memoryssa", 69 "Memory SSA Printer", false, false) 70INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) 71INITIALIZE_PASS_END(MemorySSAPrinterLegacyPass, "print-memoryssa", 72 "Memory SSA Printer", false, false) 73 74static cl::opt<unsigned> MaxCheckLimit( 75 "memssa-check-limit", cl::Hidden, cl::init(100), 76 cl::desc("The maximum number of stores/phis MemorySSA" 77 "will consider trying to walk past (default = 100)")); 78 79static cl::opt<bool> 80 VerifyMemorySSA("verify-memoryssa", cl::init(false), cl::Hidden, 81 cl::desc("Verify MemorySSA in legacy printer pass.")); 82 83namespace llvm { 84 85/// \brief An assembly annotator class to print Memory SSA information in 86/// comments. 87class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter { 88 friend class MemorySSA; 89 90 const MemorySSA *MSSA; 91 92public: 93 MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {} 94 95 void emitBasicBlockStartAnnot(const BasicBlock *BB, 96 formatted_raw_ostream &OS) override { 97 if (MemoryAccess *MA = MSSA->getMemoryAccess(BB)) 98 OS << "; " << *MA << "\n"; 99 } 100 101 void emitInstructionAnnot(const Instruction *I, 102 formatted_raw_ostream &OS) override { 103 if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) 104 OS << "; " << *MA << "\n"; 105 } 106}; 107 108} // end namespace llvm 109 110namespace { 111 112/// Our current alias analysis API differentiates heavily between calls and 113/// non-calls, and functions called on one usually assert on the other. 114/// This class encapsulates the distinction to simplify other code that wants 115/// "Memory affecting instructions and related data" to use as a key. 116/// For example, this class is used as a densemap key in the use optimizer. 117class MemoryLocOrCall { 118public: 119 bool IsCall = false; 120 121 MemoryLocOrCall() = default; 122 MemoryLocOrCall(MemoryUseOrDef *MUD) 123 : MemoryLocOrCall(MUD->getMemoryInst()) {} 124 MemoryLocOrCall(const MemoryUseOrDef *MUD) 125 : MemoryLocOrCall(MUD->getMemoryInst()) {} 126 127 MemoryLocOrCall(Instruction *Inst) { 128 if (ImmutableCallSite(Inst)) { 129 IsCall = true; 130 CS = ImmutableCallSite(Inst); 131 } else { 132 IsCall = false; 133 // There is no such thing as a memorylocation for a fence inst, and it is 134 // unique in that regard. 135 if (!isa<FenceInst>(Inst)) 136 Loc = MemoryLocation::get(Inst); 137 } 138 } 139 140 explicit MemoryLocOrCall(const MemoryLocation &Loc) : Loc(Loc) {} 141 142 ImmutableCallSite getCS() const { 143 assert(IsCall); 144 return CS; 145 } 146 147 MemoryLocation getLoc() const { 148 assert(!IsCall); 149 return Loc; 150 } 151 152 bool operator==(const MemoryLocOrCall &Other) const { 153 if (IsCall != Other.IsCall) 154 return false; 155 156 if (!IsCall) 157 return Loc == Other.Loc; 158 159 if (CS.getCalledValue() != Other.CS.getCalledValue()) 160 return false; 161 162 return CS.arg_size() == Other.CS.arg_size() && 163 std::equal(CS.arg_begin(), CS.arg_end(), Other.CS.arg_begin()); 164 } 165 166private: 167 union { 168 ImmutableCallSite CS; 169 MemoryLocation Loc; 170 }; 171}; 172 173} // end anonymous namespace 174 175namespace llvm { 176 177template <> struct DenseMapInfo<MemoryLocOrCall> { 178 static inline MemoryLocOrCall getEmptyKey() { 179 return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getEmptyKey()); 180 } 181 182 static inline MemoryLocOrCall getTombstoneKey() { 183 return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getTombstoneKey()); 184 } 185 186 static unsigned getHashValue(const MemoryLocOrCall &MLOC) { 187 if (!MLOC.IsCall) 188 return hash_combine( 189 MLOC.IsCall, 190 DenseMapInfo<MemoryLocation>::getHashValue(MLOC.getLoc())); 191 192 hash_code hash = 193 hash_combine(MLOC.IsCall, DenseMapInfo<const Value *>::getHashValue( 194 MLOC.getCS().getCalledValue())); 195 196 for (const Value *Arg : MLOC.getCS().args()) 197 hash = hash_combine(hash, DenseMapInfo<const Value *>::getHashValue(Arg)); 198 return hash; 199 } 200 201 static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) { 202 return LHS == RHS; 203 } 204}; 205 206} // end namespace llvm 207 208/// This does one-way checks to see if Use could theoretically be hoisted above 209/// MayClobber. This will not check the other way around. 210/// 211/// This assumes that, for the purposes of MemorySSA, Use comes directly after 212/// MayClobber, with no potentially clobbering operations in between them. 213/// (Where potentially clobbering ops are memory barriers, aliased stores, etc.) 214static bool areLoadsReorderable(const LoadInst *Use, 215 const LoadInst *MayClobber) { 216 bool VolatileUse = Use->isVolatile(); 217 bool VolatileClobber = MayClobber->isVolatile(); 218 // Volatile operations may never be reordered with other volatile operations. 219 if (VolatileUse && VolatileClobber) 220 return false; 221 // Otherwise, volatile doesn't matter here. From the language reference: 222 // 'optimizers may change the order of volatile operations relative to 223 // non-volatile operations.'" 224 225 // If a load is seq_cst, it cannot be moved above other loads. If its ordering 226 // is weaker, it can be moved above other loads. We just need to be sure that 227 // MayClobber isn't an acquire load, because loads can't be moved above 228 // acquire loads. 229 // 230 // Note that this explicitly *does* allow the free reordering of monotonic (or 231 // weaker) loads of the same address. 232 bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent; 233 bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(), 234 AtomicOrdering::Acquire); 235 return !(SeqCstUse || MayClobberIsAcquire); 236} 237 238static bool instructionClobbersQuery(MemoryDef *MD, 239 const MemoryLocation &UseLoc, 240 const Instruction *UseInst, 241 AliasAnalysis &AA) { 242 Instruction *DefInst = MD->getMemoryInst(); 243 assert(DefInst && "Defining instruction not actually an instruction"); 244 ImmutableCallSite UseCS(UseInst); 245 246 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) { 247 // These intrinsics will show up as affecting memory, but they are just 248 // markers. 249 switch (II->getIntrinsicID()) { 250 case Intrinsic::lifetime_start: 251 if (UseCS) 252 return false; 253 return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc); 254 case Intrinsic::lifetime_end: 255 case Intrinsic::invariant_start: 256 case Intrinsic::invariant_end: 257 case Intrinsic::assume: 258 return false; 259 default: 260 break; 261 } 262 } 263 264 if (UseCS) { 265 ModRefInfo I = AA.getModRefInfo(DefInst, UseCS); 266 return isModOrRefSet(I); 267 } 268 269 if (auto *DefLoad = dyn_cast<LoadInst>(DefInst)) 270 if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) 271 return !areLoadsReorderable(UseLoad, DefLoad); 272 273 return isModSet(AA.getModRefInfo(DefInst, UseLoc)); 274} 275 276static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU, 277 const MemoryLocOrCall &UseMLOC, 278 AliasAnalysis &AA) { 279 // FIXME: This is a temporary hack to allow a single instructionClobbersQuery 280 // to exist while MemoryLocOrCall is pushed through places. 281 if (UseMLOC.IsCall) 282 return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(), 283 AA); 284 return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(), 285 AA); 286} 287 288// Return true when MD may alias MU, return false otherwise. 289bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, 290 AliasAnalysis &AA) { 291 return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA); 292} 293 294namespace { 295 296struct UpwardsMemoryQuery { 297 // True if our original query started off as a call 298 bool IsCall = false; 299 // The pointer location we started the query with. This will be empty if 300 // IsCall is true. 301 MemoryLocation StartingLoc; 302 // This is the instruction we were querying about. 303 const Instruction *Inst = nullptr; 304 // The MemoryAccess we actually got called with, used to test local domination 305 const MemoryAccess *OriginalAccess = nullptr; 306 307 UpwardsMemoryQuery() = default; 308 309 UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access) 310 : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) { 311 if (!IsCall) 312 StartingLoc = MemoryLocation::get(Inst); 313 } 314}; 315 316} // end anonymous namespace 317 318static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc, 319 AliasAnalysis &AA) { 320 Instruction *Inst = MD->getMemoryInst(); 321 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 322 switch (II->getIntrinsicID()) { 323 case Intrinsic::lifetime_end: 324 return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), Loc); 325 default: 326 return false; 327 } 328 } 329 return false; 330} 331 332static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysis &AA, 333 const Instruction *I) { 334 // If the memory can't be changed, then loads of the memory can't be 335 // clobbered. 336 // 337 // FIXME: We should handle invariant groups, as well. It's a bit harder, 338 // because we need to pay close attention to invariant group barriers. 339 return isa<LoadInst>(I) && (I->getMetadata(LLVMContext::MD_invariant_load) || 340 AA.pointsToConstantMemory(cast<LoadInst>(I)-> 341 getPointerOperand())); 342} 343 344/// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing 345/// inbetween `Start` and `ClobberAt` can clobbers `Start`. 346/// 347/// This is meant to be as simple and self-contained as possible. Because it 348/// uses no cache, etc., it can be relatively expensive. 349/// 350/// \param Start The MemoryAccess that we want to walk from. 351/// \param ClobberAt A clobber for Start. 352/// \param StartLoc The MemoryLocation for Start. 353/// \param MSSA The MemorySSA isntance that Start and ClobberAt belong to. 354/// \param Query The UpwardsMemoryQuery we used for our search. 355/// \param AA The AliasAnalysis we used for our search. 356static void LLVM_ATTRIBUTE_UNUSED 357checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt, 358 const MemoryLocation &StartLoc, const MemorySSA &MSSA, 359 const UpwardsMemoryQuery &Query, AliasAnalysis &AA) { 360 assert(MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?"); 361 362 if (MSSA.isLiveOnEntryDef(Start)) { 363 assert(MSSA.isLiveOnEntryDef(ClobberAt) && 364 "liveOnEntry must clobber itself"); 365 return; 366 } 367 368 bool FoundClobber = false; 369 DenseSet<MemoryAccessPair> VisitedPhis; 370 SmallVector<MemoryAccessPair, 8> Worklist; 371 Worklist.emplace_back(Start, StartLoc); 372 // Walk all paths from Start to ClobberAt, while looking for clobbers. If one 373 // is found, complain. 374 while (!Worklist.empty()) { 375 MemoryAccessPair MAP = Worklist.pop_back_val(); 376 // All we care about is that nothing from Start to ClobberAt clobbers Start. 377 // We learn nothing from revisiting nodes. 378 if (!VisitedPhis.insert(MAP).second) 379 continue; 380 381 for (MemoryAccess *MA : def_chain(MAP.first)) { 382 if (MA == ClobberAt) { 383 if (auto *MD = dyn_cast<MemoryDef>(MA)) { 384 // instructionClobbersQuery isn't essentially free, so don't use `|=`, 385 // since it won't let us short-circuit. 386 // 387 // Also, note that this can't be hoisted out of the `Worklist` loop, 388 // since MD may only act as a clobber for 1 of N MemoryLocations. 389 FoundClobber = 390 FoundClobber || MSSA.isLiveOnEntryDef(MD) || 391 instructionClobbersQuery(MD, MAP.second, Query.Inst, AA); 392 } 393 break; 394 } 395 396 // We should never hit liveOnEntry, unless it's the clobber. 397 assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?"); 398 399 if (auto *MD = dyn_cast<MemoryDef>(MA)) { 400 (void)MD; 401 assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) && 402 "Found clobber before reaching ClobberAt!"); 403 continue; 404 } 405 406 assert(isa<MemoryPhi>(MA)); 407 Worklist.append(upward_defs_begin({MA, MAP.second}), upward_defs_end()); 408 } 409 } 410 411 // If ClobberAt is a MemoryPhi, we can assume something above it acted as a 412 // clobber. Otherwise, `ClobberAt` should've acted as a clobber at some point. 413 assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) && 414 "ClobberAt never acted as a clobber"); 415} 416 417namespace { 418 419/// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up 420/// in one class. 421class ClobberWalker { 422 /// Save a few bytes by using unsigned instead of size_t. 423 using ListIndex = unsigned; 424 425 /// Represents a span of contiguous MemoryDefs, potentially ending in a 426 /// MemoryPhi. 427 struct DefPath { 428 MemoryLocation Loc; 429 // Note that, because we always walk in reverse, Last will always dominate 430 // First. Also note that First and Last are inclusive. 431 MemoryAccess *First; 432 MemoryAccess *Last; 433 Optional<ListIndex> Previous; 434 435 DefPath(const MemoryLocation &Loc, MemoryAccess *First, MemoryAccess *Last, 436 Optional<ListIndex> Previous) 437 : Loc(Loc), First(First), Last(Last), Previous(Previous) {} 438 439 DefPath(const MemoryLocation &Loc, MemoryAccess *Init, 440 Optional<ListIndex> Previous) 441 : DefPath(Loc, Init, Init, Previous) {} 442 }; 443 444 const MemorySSA &MSSA; 445 AliasAnalysis &AA; 446 DominatorTree &DT; 447 UpwardsMemoryQuery *Query; 448 449 // Phi optimization bookkeeping 450 SmallVector<DefPath, 32> Paths; 451 DenseSet<ConstMemoryAccessPair> VisitedPhis; 452 453 /// Find the nearest def or phi that `From` can legally be optimized to. 454 const MemoryAccess *getWalkTarget(const MemoryPhi *From) const { 455 assert(From->getNumOperands() && "Phi with no operands?"); 456 457 BasicBlock *BB = From->getBlock(); 458 MemoryAccess *Result = MSSA.getLiveOnEntryDef(); 459 DomTreeNode *Node = DT.getNode(BB); 460 while ((Node = Node->getIDom())) { 461 auto *Defs = MSSA.getBlockDefs(Node->getBlock()); 462 if (Defs) 463 return &*Defs->rbegin(); 464 } 465 return Result; 466 } 467 468 /// Result of calling walkToPhiOrClobber. 469 struct UpwardsWalkResult { 470 /// The "Result" of the walk. Either a clobber, the last thing we walked, or 471 /// both. 472 MemoryAccess *Result; 473 bool IsKnownClobber; 474 }; 475 476 /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last. 477 /// This will update Desc.Last as it walks. It will (optionally) also stop at 478 /// StopAt. 479 /// 480 /// This does not test for whether StopAt is a clobber 481 UpwardsWalkResult 482 walkToPhiOrClobber(DefPath &Desc, 483 const MemoryAccess *StopAt = nullptr) const { 484 assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world"); 485 486 for (MemoryAccess *Current : def_chain(Desc.Last)) { 487 Desc.Last = Current; 488 if (Current == StopAt) 489 return {Current, false}; 490 491 if (auto *MD = dyn_cast<MemoryDef>(Current)) 492 if (MSSA.isLiveOnEntryDef(MD) || 493 instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA)) 494 return {MD, true}; 495 } 496 497 assert(isa<MemoryPhi>(Desc.Last) && 498 "Ended at a non-clobber that's not a phi?"); 499 return {Desc.Last, false}; 500 } 501 502 void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches, 503 ListIndex PriorNode) { 504 auto UpwardDefs = make_range(upward_defs_begin({Phi, Paths[PriorNode].Loc}), 505 upward_defs_end()); 506 for (const MemoryAccessPair &P : UpwardDefs) { 507 PausedSearches.push_back(Paths.size()); 508 Paths.emplace_back(P.second, P.first, PriorNode); 509 } 510 } 511 512 /// Represents a search that terminated after finding a clobber. This clobber 513 /// may or may not be present in the path of defs from LastNode..SearchStart, 514 /// since it may have been retrieved from cache. 515 struct TerminatedPath { 516 MemoryAccess *Clobber; 517 ListIndex LastNode; 518 }; 519 520 /// Get an access that keeps us from optimizing to the given phi. 521 /// 522 /// PausedSearches is an array of indices into the Paths array. Its incoming 523 /// value is the indices of searches that stopped at the last phi optimization 524 /// target. It's left in an unspecified state. 525 /// 526 /// If this returns None, NewPaused is a vector of searches that terminated 527 /// at StopWhere. Otherwise, NewPaused is left in an unspecified state. 528 Optional<TerminatedPath> 529 getBlockingAccess(const MemoryAccess *StopWhere, 530 SmallVectorImpl<ListIndex> &PausedSearches, 531 SmallVectorImpl<ListIndex> &NewPaused, 532 SmallVectorImpl<TerminatedPath> &Terminated) { 533 assert(!PausedSearches.empty() && "No searches to continue?"); 534 535 // BFS vs DFS really doesn't make a difference here, so just do a DFS with 536 // PausedSearches as our stack. 537 while (!PausedSearches.empty()) { 538 ListIndex PathIndex = PausedSearches.pop_back_val(); 539 DefPath &Node = Paths[PathIndex]; 540 541 // If we've already visited this path with this MemoryLocation, we don't 542 // need to do so again. 543 // 544 // NOTE: That we just drop these paths on the ground makes caching 545 // behavior sporadic. e.g. given a diamond: 546 // A 547 // B C 548 // D 549 // 550 // ...If we walk D, B, A, C, we'll only cache the result of phi 551 // optimization for A, B, and D; C will be skipped because it dies here. 552 // This arguably isn't the worst thing ever, since: 553 // - We generally query things in a top-down order, so if we got below D 554 // without needing cache entries for {C, MemLoc}, then chances are 555 // that those cache entries would end up ultimately unused. 556 // - We still cache things for A, so C only needs to walk up a bit. 557 // If this behavior becomes problematic, we can fix without a ton of extra 558 // work. 559 if (!VisitedPhis.insert({Node.Last, Node.Loc}).second) 560 continue; 561 562 UpwardsWalkResult Res = walkToPhiOrClobber(Node, /*StopAt=*/StopWhere); 563 if (Res.IsKnownClobber) { 564 assert(Res.Result != StopWhere); 565 // If this wasn't a cache hit, we hit a clobber when walking. That's a 566 // failure. 567 TerminatedPath Term{Res.Result, PathIndex}; 568 if (!MSSA.dominates(Res.Result, StopWhere)) 569 return Term; 570 571 // Otherwise, it's a valid thing to potentially optimize to. 572 Terminated.push_back(Term); 573 continue; 574 } 575 576 if (Res.Result == StopWhere) { 577 // We've hit our target. Save this path off for if we want to continue 578 // walking. 579 NewPaused.push_back(PathIndex); 580 continue; 581 } 582 583 assert(!MSSA.isLiveOnEntryDef(Res.Result) && "liveOnEntry is a clobber"); 584 addSearches(cast<MemoryPhi>(Res.Result), PausedSearches, PathIndex); 585 } 586 587 return None; 588 } 589 590 template <typename T, typename Walker> 591 struct generic_def_path_iterator 592 : public iterator_facade_base<generic_def_path_iterator<T, Walker>, 593 std::forward_iterator_tag, T *> { 594 generic_def_path_iterator() = default; 595 generic_def_path_iterator(Walker *W, ListIndex N) : W(W), N(N) {} 596 597 T &operator*() const { return curNode(); } 598 599 generic_def_path_iterator &operator++() { 600 N = curNode().Previous; 601 return *this; 602 } 603 604 bool operator==(const generic_def_path_iterator &O) const { 605 if (N.hasValue() != O.N.hasValue()) 606 return false; 607 return !N.hasValue() || *N == *O.N; 608 } 609 610 private: 611 T &curNode() const { return W->Paths[*N]; } 612 613 Walker *W = nullptr; 614 Optional<ListIndex> N = None; 615 }; 616 617 using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>; 618 using const_def_path_iterator = 619 generic_def_path_iterator<const DefPath, const ClobberWalker>; 620 621 iterator_range<def_path_iterator> def_path(ListIndex From) { 622 return make_range(def_path_iterator(this, From), def_path_iterator()); 623 } 624 625 iterator_range<const_def_path_iterator> const_def_path(ListIndex From) const { 626 return make_range(const_def_path_iterator(this, From), 627 const_def_path_iterator()); 628 } 629 630 struct OptznResult { 631 /// The path that contains our result. 632 TerminatedPath PrimaryClobber; 633 /// The paths that we can legally cache back from, but that aren't 634 /// necessarily the result of the Phi optimization. 635 SmallVector<TerminatedPath, 4> OtherClobbers; 636 }; 637 638 ListIndex defPathIndex(const DefPath &N) const { 639 // The assert looks nicer if we don't need to do &N 640 const DefPath *NP = &N; 641 assert(!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() && 642 "Out of bounds DefPath!"); 643 return NP - &Paths.front(); 644 } 645 646 /// Try to optimize a phi as best as we can. Returns a SmallVector of Paths 647 /// that act as legal clobbers. Note that this won't return *all* clobbers. 648 /// 649 /// Phi optimization algorithm tl;dr: 650 /// - Find the earliest def/phi, A, we can optimize to 651 /// - Find if all paths from the starting memory access ultimately reach A 652 /// - If not, optimization isn't possible. 653 /// - Otherwise, walk from A to another clobber or phi, A'. 654 /// - If A' is a def, we're done. 655 /// - If A' is a phi, try to optimize it. 656 /// 657 /// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path 658 /// terminates when a MemoryAccess that clobbers said MemoryLocation is found. 659 OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start, 660 const MemoryLocation &Loc) { 661 assert(Paths.empty() && VisitedPhis.empty() && 662 "Reset the optimization state."); 663 664 Paths.emplace_back(Loc, Start, Phi, None); 665 // Stores how many "valid" optimization nodes we had prior to calling 666 // addSearches/getBlockingAccess. Necessary for caching if we had a blocker. 667 auto PriorPathsSize = Paths.size(); 668 669 SmallVector<ListIndex, 16> PausedSearches; 670 SmallVector<ListIndex, 8> NewPaused; 671 SmallVector<TerminatedPath, 4> TerminatedPaths; 672 673 addSearches(Phi, PausedSearches, 0); 674 675 // Moves the TerminatedPath with the "most dominated" Clobber to the end of 676 // Paths. 677 auto MoveDominatedPathToEnd = [&](SmallVectorImpl<TerminatedPath> &Paths) { 678 assert(!Paths.empty() && "Need a path to move"); 679 auto Dom = Paths.begin(); 680 for (auto I = std::next(Dom), E = Paths.end(); I != E; ++I) 681 if (!MSSA.dominates(I->Clobber, Dom->Clobber)) 682 Dom = I; 683 auto Last = Paths.end() - 1; 684 if (Last != Dom) 685 std::iter_swap(Last, Dom); 686 }; 687 688 MemoryPhi *Current = Phi; 689 while (true) { 690 assert(!MSSA.isLiveOnEntryDef(Current) && 691 "liveOnEntry wasn't treated as a clobber?"); 692 693 const auto *Target = getWalkTarget(Current); 694 // If a TerminatedPath doesn't dominate Target, then it wasn't a legal 695 // optimization for the prior phi. 696 assert(all_of(TerminatedPaths, [&](const TerminatedPath &P) { 697 return MSSA.dominates(P.Clobber, Target); 698 })); 699 700 // FIXME: This is broken, because the Blocker may be reported to be 701 // liveOnEntry, and we'll happily wait for that to disappear (read: never) 702 // For the moment, this is fine, since we do nothing with blocker info. 703 if (Optional<TerminatedPath> Blocker = getBlockingAccess( 704 Target, PausedSearches, NewPaused, TerminatedPaths)) { 705 706 // Find the node we started at. We can't search based on N->Last, since 707 // we may have gone around a loop with a different MemoryLocation. 708 auto Iter = find_if(def_path(Blocker->LastNode), [&](const DefPath &N) { 709 return defPathIndex(N) < PriorPathsSize; 710 }); 711 assert(Iter != def_path_iterator()); 712 713 DefPath &CurNode = *Iter; 714 assert(CurNode.Last == Current); 715 716 // Two things: 717 // A. We can't reliably cache all of NewPaused back. Consider a case 718 // where we have two paths in NewPaused; one of which can't optimize 719 // above this phi, whereas the other can. If we cache the second path 720 // back, we'll end up with suboptimal cache entries. We can handle 721 // cases like this a bit better when we either try to find all 722 // clobbers that block phi optimization, or when our cache starts 723 // supporting unfinished searches. 724 // B. We can't reliably cache TerminatedPaths back here without doing 725 // extra checks; consider a case like: 726 // T 727 // / \ 728 // D C 729 // \ / 730 // S 731 // Where T is our target, C is a node with a clobber on it, D is a 732 // diamond (with a clobber *only* on the left or right node, N), and 733 // S is our start. Say we walk to D, through the node opposite N 734 // (read: ignoring the clobber), and see a cache entry in the top 735 // node of D. That cache entry gets put into TerminatedPaths. We then 736 // walk up to C (N is later in our worklist), find the clobber, and 737 // quit. If we append TerminatedPaths to OtherClobbers, we'll cache 738 // the bottom part of D to the cached clobber, ignoring the clobber 739 // in N. Again, this problem goes away if we start tracking all 740 // blockers for a given phi optimization. 741 TerminatedPath Result{CurNode.Last, defPathIndex(CurNode)}; 742 return {Result, {}}; 743 } 744 745 // If there's nothing left to search, then all paths led to valid clobbers 746 // that we got from our cache; pick the nearest to the start, and allow 747 // the rest to be cached back. 748 if (NewPaused.empty()) { 749 MoveDominatedPathToEnd(TerminatedPaths); 750 TerminatedPath Result = TerminatedPaths.pop_back_val(); 751 return {Result, std::move(TerminatedPaths)}; 752 } 753 754 MemoryAccess *DefChainEnd = nullptr; 755 SmallVector<TerminatedPath, 4> Clobbers; 756 for (ListIndex Paused : NewPaused) { 757 UpwardsWalkResult WR = walkToPhiOrClobber(Paths[Paused]); 758 if (WR.IsKnownClobber) 759 Clobbers.push_back({WR.Result, Paused}); 760 else 761 // Micro-opt: If we hit the end of the chain, save it. 762 DefChainEnd = WR.Result; 763 } 764 765 if (!TerminatedPaths.empty()) { 766 // If we couldn't find the dominating phi/liveOnEntry in the above loop, 767 // do it now. 768 if (!DefChainEnd) 769 for (auto *MA : def_chain(const_cast<MemoryAccess *>(Target))) 770 DefChainEnd = MA; 771 772 // If any of the terminated paths don't dominate the phi we'll try to 773 // optimize, we need to figure out what they are and quit. 774 const BasicBlock *ChainBB = DefChainEnd->getBlock(); 775 for (const TerminatedPath &TP : TerminatedPaths) { 776 // Because we know that DefChainEnd is as "high" as we can go, we 777 // don't need local dominance checks; BB dominance is sufficient. 778 if (DT.dominates(ChainBB, TP.Clobber->getBlock())) 779 Clobbers.push_back(TP); 780 } 781 } 782 783 // If we have clobbers in the def chain, find the one closest to Current 784 // and quit. 785 if (!Clobbers.empty()) { 786 MoveDominatedPathToEnd(Clobbers); 787 TerminatedPath Result = Clobbers.pop_back_val(); 788 return {Result, std::move(Clobbers)}; 789 } 790 791 assert(all_of(NewPaused, 792 [&](ListIndex I) { return Paths[I].Last == DefChainEnd; })); 793 794 // Because liveOnEntry is a clobber, this must be a phi. 795 auto *DefChainPhi = cast<MemoryPhi>(DefChainEnd); 796 797 PriorPathsSize = Paths.size(); 798 PausedSearches.clear(); 799 for (ListIndex I : NewPaused) 800 addSearches(DefChainPhi, PausedSearches, I); 801 NewPaused.clear(); 802 803 Current = DefChainPhi; 804 } 805 } 806 807 void verifyOptResult(const OptznResult &R) const { 808 assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) { 809 return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber); 810 })); 811 } 812 813 void resetPhiOptznState() { 814 Paths.clear(); 815 VisitedPhis.clear(); 816 } 817 818public: 819 ClobberWalker(const MemorySSA &MSSA, AliasAnalysis &AA, DominatorTree &DT) 820 : MSSA(MSSA), AA(AA), DT(DT) {} 821 822 void reset() {} 823 824 /// Finds the nearest clobber for the given query, optimizing phis if 825 /// possible. 826 MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q) { 827 Query = &Q; 828 829 MemoryAccess *Current = Start; 830 // This walker pretends uses don't exist. If we're handed one, silently grab 831 // its def. (This has the nice side-effect of ensuring we never cache uses) 832 if (auto *MU = dyn_cast<MemoryUse>(Start)) 833 Current = MU->getDefiningAccess(); 834 835 DefPath FirstDesc(Q.StartingLoc, Current, Current, None); 836 // Fast path for the overly-common case (no crazy phi optimization 837 // necessary) 838 UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc); 839 MemoryAccess *Result; 840 if (WalkResult.IsKnownClobber) { 841 Result = WalkResult.Result; 842 } else { 843 OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last), 844 Current, Q.StartingLoc); 845 verifyOptResult(OptRes); 846 resetPhiOptznState(); 847 Result = OptRes.PrimaryClobber.Clobber; 848 } 849 850#ifdef EXPENSIVE_CHECKS 851 checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA); 852#endif 853 return Result; 854 } 855 856 void verify(const MemorySSA *MSSA) { assert(MSSA == &this->MSSA); } 857}; 858 859struct RenamePassData { 860 DomTreeNode *DTN; 861 DomTreeNode::const_iterator ChildIt; 862 MemoryAccess *IncomingVal; 863 864 RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It, 865 MemoryAccess *M) 866 : DTN(D), ChildIt(It), IncomingVal(M) {} 867 868 void swap(RenamePassData &RHS) { 869 std::swap(DTN, RHS.DTN); 870 std::swap(ChildIt, RHS.ChildIt); 871 std::swap(IncomingVal, RHS.IncomingVal); 872 } 873}; 874 875} // end anonymous namespace 876 877namespace llvm { 878 879/// \brief A MemorySSAWalker that does AA walks to disambiguate accesses. It no 880/// longer does caching on its own, 881/// but the name has been retained for the moment. 882class MemorySSA::CachingWalker final : public MemorySSAWalker { 883 ClobberWalker Walker; 884 bool AutoResetWalker = true; 885 886 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &); 887 888public: 889 CachingWalker(MemorySSA *, AliasAnalysis *, DominatorTree *); 890 ~CachingWalker() override = default; 891 892 using MemorySSAWalker::getClobberingMemoryAccess; 893 894 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override; 895 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, 896 const MemoryLocation &) override; 897 void invalidateInfo(MemoryAccess *) override; 898 899 /// Whether we call resetClobberWalker() after each time we *actually* walk to 900 /// answer a clobber query. 901 void setAutoResetWalker(bool AutoReset) { AutoResetWalker = AutoReset; } 902 903 /// Drop the walker's persistent data structures. 904 void resetClobberWalker() { Walker.reset(); } 905 906 void verify(const MemorySSA *MSSA) override { 907 MemorySSAWalker::verify(MSSA); 908 Walker.verify(MSSA); 909 } 910}; 911 912} // end namespace llvm 913 914void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal, 915 bool RenameAllUses) { 916 // Pass through values to our successors 917 for (const BasicBlock *S : successors(BB)) { 918 auto It = PerBlockAccesses.find(S); 919 // Rename the phi nodes in our successor block 920 if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front())) 921 continue; 922 AccessList *Accesses = It->second.get(); 923 auto *Phi = cast<MemoryPhi>(&Accesses->front()); 924 if (RenameAllUses) { 925 int PhiIndex = Phi->getBasicBlockIndex(BB); 926 assert(PhiIndex != -1 && "Incomplete phi during partial rename"); 927 Phi->setIncomingValue(PhiIndex, IncomingVal); 928 } else 929 Phi->addIncoming(IncomingVal, BB); 930 } 931} 932 933/// \brief Rename a single basic block into MemorySSA form. 934/// Uses the standard SSA renaming algorithm. 935/// \returns The new incoming value. 936MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, MemoryAccess *IncomingVal, 937 bool RenameAllUses) { 938 auto It = PerBlockAccesses.find(BB); 939 // Skip most processing if the list is empty. 940 if (It != PerBlockAccesses.end()) { 941 AccessList *Accesses = It->second.get(); 942 for (MemoryAccess &L : *Accesses) { 943 if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&L)) { 944 if (MUD->getDefiningAccess() == nullptr || RenameAllUses) 945 MUD->setDefiningAccess(IncomingVal); 946 if (isa<MemoryDef>(&L)) 947 IncomingVal = &L; 948 } else { 949 IncomingVal = &L; 950 } 951 } 952 } 953 return IncomingVal; 954} 955 956/// \brief This is the standard SSA renaming algorithm. 957/// 958/// We walk the dominator tree in preorder, renaming accesses, and then filling 959/// in phi nodes in our successors. 960void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal, 961 SmallPtrSetImpl<BasicBlock *> &Visited, 962 bool SkipVisited, bool RenameAllUses) { 963 SmallVector<RenamePassData, 32> WorkStack; 964 // Skip everything if we already renamed this block and we are skipping. 965 // Note: You can't sink this into the if, because we need it to occur 966 // regardless of whether we skip blocks or not. 967 bool AlreadyVisited = !Visited.insert(Root->getBlock()).second; 968 if (SkipVisited && AlreadyVisited) 969 return; 970 971 IncomingVal = renameBlock(Root->getBlock(), IncomingVal, RenameAllUses); 972 renameSuccessorPhis(Root->getBlock(), IncomingVal, RenameAllUses); 973 WorkStack.push_back({Root, Root->begin(), IncomingVal}); 974 975 while (!WorkStack.empty()) { 976 DomTreeNode *Node = WorkStack.back().DTN; 977 DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt; 978 IncomingVal = WorkStack.back().IncomingVal; 979 980 if (ChildIt == Node->end()) { 981 WorkStack.pop_back(); 982 } else { 983 DomTreeNode *Child = *ChildIt; 984 ++WorkStack.back().ChildIt; 985 BasicBlock *BB = Child->getBlock(); 986 // Note: You can't sink this into the if, because we need it to occur 987 // regardless of whether we skip blocks or not. 988 AlreadyVisited = !Visited.insert(BB).second; 989 if (SkipVisited && AlreadyVisited) { 990 // We already visited this during our renaming, which can happen when 991 // being asked to rename multiple blocks. Figure out the incoming val, 992 // which is the last def. 993 // Incoming value can only change if there is a block def, and in that 994 // case, it's the last block def in the list. 995 if (auto *BlockDefs = getWritableBlockDefs(BB)) 996 IncomingVal = &*BlockDefs->rbegin(); 997 } else 998 IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses); 999 renameSuccessorPhis(BB, IncomingVal, RenameAllUses); 1000 WorkStack.push_back({Child, Child->begin(), IncomingVal}); 1001 } 1002 } 1003} 1004 1005/// \brief This handles unreachable block accesses by deleting phi nodes in 1006/// unreachable blocks, and marking all other unreachable MemoryAccess's as 1007/// being uses of the live on entry definition. 1008void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) { 1009 assert(!DT->isReachableFromEntry(BB) && 1010 "Reachable block found while handling unreachable blocks"); 1011 1012 // Make sure phi nodes in our reachable successors end up with a 1013 // LiveOnEntryDef for our incoming edge, even though our block is forward 1014 // unreachable. We could just disconnect these blocks from the CFG fully, 1015 // but we do not right now. 1016 for (const BasicBlock *S : successors(BB)) { 1017 if (!DT->isReachableFromEntry(S)) 1018 continue; 1019 auto It = PerBlockAccesses.find(S); 1020 // Rename the phi nodes in our successor block 1021 if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front())) 1022 continue; 1023 AccessList *Accesses = It->second.get(); 1024 auto *Phi = cast<MemoryPhi>(&Accesses->front()); 1025 Phi->addIncoming(LiveOnEntryDef.get(), BB); 1026 } 1027 1028 auto It = PerBlockAccesses.find(BB); 1029 if (It == PerBlockAccesses.end()) 1030 return; 1031 1032 auto &Accesses = It->second; 1033 for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) { 1034 auto Next = std::next(AI); 1035 // If we have a phi, just remove it. We are going to replace all 1036 // users with live on entry. 1037 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(AI)) 1038 UseOrDef->setDefiningAccess(LiveOnEntryDef.get()); 1039 else 1040 Accesses->erase(AI); 1041 AI = Next; 1042 } 1043} 1044 1045MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT) 1046 : AA(AA), DT(DT), F(Func), LiveOnEntryDef(nullptr), Walker(nullptr), 1047 NextID(INVALID_MEMORYACCESS_ID) { 1048 buildMemorySSA(); 1049} 1050 1051MemorySSA::~MemorySSA() { 1052 // Drop all our references 1053 for (const auto &Pair : PerBlockAccesses) 1054 for (MemoryAccess &MA : *Pair.second) 1055 MA.dropAllReferences(); 1056} 1057 1058MemorySSA::AccessList *MemorySSA::getOrCreateAccessList(const BasicBlock *BB) { 1059 auto Res = PerBlockAccesses.insert(std::make_pair(BB, nullptr)); 1060 1061 if (Res.second) 1062 Res.first->second = llvm::make_unique<AccessList>(); 1063 return Res.first->second.get(); 1064} 1065 1066MemorySSA::DefsList *MemorySSA::getOrCreateDefsList(const BasicBlock *BB) { 1067 auto Res = PerBlockDefs.insert(std::make_pair(BB, nullptr)); 1068 1069 if (Res.second) 1070 Res.first->second = llvm::make_unique<DefsList>(); 1071 return Res.first->second.get(); 1072} 1073 1074namespace llvm { 1075 1076/// This class is a batch walker of all MemoryUse's in the program, and points 1077/// their defining access at the thing that actually clobbers them. Because it 1078/// is a batch walker that touches everything, it does not operate like the 1079/// other walkers. This walker is basically performing a top-down SSA renaming 1080/// pass, where the version stack is used as the cache. This enables it to be 1081/// significantly more time and memory efficient than using the regular walker, 1082/// which is walking bottom-up. 1083class MemorySSA::OptimizeUses { 1084public: 1085 OptimizeUses(MemorySSA *MSSA, MemorySSAWalker *Walker, AliasAnalysis *AA, 1086 DominatorTree *DT) 1087 : MSSA(MSSA), Walker(Walker), AA(AA), DT(DT) { 1088 Walker = MSSA->getWalker(); 1089 } 1090 1091 void optimizeUses(); 1092 1093private: 1094 /// This represents where a given memorylocation is in the stack. 1095 struct MemlocStackInfo { 1096 // This essentially is keeping track of versions of the stack. Whenever 1097 // the stack changes due to pushes or pops, these versions increase. 1098 unsigned long StackEpoch; 1099 unsigned long PopEpoch; 1100 // This is the lower bound of places on the stack to check. It is equal to 1101 // the place the last stack walk ended. 1102 // Note: Correctness depends on this being initialized to 0, which densemap 1103 // does 1104 unsigned long LowerBound; 1105 const BasicBlock *LowerBoundBlock; 1106 // This is where the last walk for this memory location ended. 1107 unsigned long LastKill; 1108 bool LastKillValid; 1109 }; 1110 1111 void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &, 1112 SmallVectorImpl<MemoryAccess *> &, 1113 DenseMap<MemoryLocOrCall, MemlocStackInfo> &); 1114 1115 MemorySSA *MSSA; 1116 MemorySSAWalker *Walker; 1117 AliasAnalysis *AA; 1118 DominatorTree *DT; 1119}; 1120 1121} // end namespace llvm 1122 1123/// Optimize the uses in a given block This is basically the SSA renaming 1124/// algorithm, with one caveat: We are able to use a single stack for all 1125/// MemoryUses. This is because the set of *possible* reaching MemoryDefs is 1126/// the same for every MemoryUse. The *actual* clobbering MemoryDef is just 1127/// going to be some position in that stack of possible ones. 1128/// 1129/// We track the stack positions that each MemoryLocation needs 1130/// to check, and last ended at. This is because we only want to check the 1131/// things that changed since last time. The same MemoryLocation should 1132/// get clobbered by the same store (getModRefInfo does not use invariantness or 1133/// things like this, and if they start, we can modify MemoryLocOrCall to 1134/// include relevant data) 1135void MemorySSA::OptimizeUses::optimizeUsesInBlock( 1136 const BasicBlock *BB, unsigned long &StackEpoch, unsigned long &PopEpoch, 1137 SmallVectorImpl<MemoryAccess *> &VersionStack, 1138 DenseMap<MemoryLocOrCall, MemlocStackInfo> &LocStackInfo) { 1139 1140 /// If no accesses, nothing to do. 1141 MemorySSA::AccessList *Accesses = MSSA->getWritableBlockAccesses(BB); 1142 if (Accesses == nullptr) 1143 return; 1144 1145 // Pop everything that doesn't dominate the current block off the stack, 1146 // increment the PopEpoch to account for this. 1147 while (true) { 1148 assert( 1149 !VersionStack.empty() && 1150 "Version stack should have liveOnEntry sentinel dominating everything"); 1151 BasicBlock *BackBlock = VersionStack.back()->getBlock(); 1152 if (DT->dominates(BackBlock, BB)) 1153 break; 1154 while (VersionStack.back()->getBlock() == BackBlock) 1155 VersionStack.pop_back(); 1156 ++PopEpoch; 1157 } 1158 1159 for (MemoryAccess &MA : *Accesses) { 1160 auto *MU = dyn_cast<MemoryUse>(&MA); 1161 if (!MU) { 1162 VersionStack.push_back(&MA); 1163 ++StackEpoch; 1164 continue; 1165 } 1166 1167 if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) { 1168 MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true); 1169 continue; 1170 } 1171 1172 MemoryLocOrCall UseMLOC(MU); 1173 auto &LocInfo = LocStackInfo[UseMLOC]; 1174 // If the pop epoch changed, it means we've removed stuff from top of 1175 // stack due to changing blocks. We may have to reset the lower bound or 1176 // last kill info. 1177 if (LocInfo.PopEpoch != PopEpoch) { 1178 LocInfo.PopEpoch = PopEpoch; 1179 LocInfo.StackEpoch = StackEpoch; 1180 // If the lower bound was in something that no longer dominates us, we 1181 // have to reset it. 1182 // We can't simply track stack size, because the stack may have had 1183 // pushes/pops in the meantime. 1184 // XXX: This is non-optimal, but only is slower cases with heavily 1185 // branching dominator trees. To get the optimal number of queries would 1186 // be to make lowerbound and lastkill a per-loc stack, and pop it until 1187 // the top of that stack dominates us. This does not seem worth it ATM. 1188 // A much cheaper optimization would be to always explore the deepest 1189 // branch of the dominator tree first. This will guarantee this resets on 1190 // the smallest set of blocks. 1191 if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB && 1192 !DT->dominates(LocInfo.LowerBoundBlock, BB)) { 1193 // Reset the lower bound of things to check. 1194 // TODO: Some day we should be able to reset to last kill, rather than 1195 // 0. 1196 LocInfo.LowerBound = 0; 1197 LocInfo.LowerBoundBlock = VersionStack[0]->getBlock(); 1198 LocInfo.LastKillValid = false; 1199 } 1200 } else if (LocInfo.StackEpoch != StackEpoch) { 1201 // If all that has changed is the StackEpoch, we only have to check the 1202 // new things on the stack, because we've checked everything before. In 1203 // this case, the lower bound of things to check remains the same. 1204 LocInfo.PopEpoch = PopEpoch; 1205 LocInfo.StackEpoch = StackEpoch; 1206 } 1207 if (!LocInfo.LastKillValid) { 1208 LocInfo.LastKill = VersionStack.size() - 1; 1209 LocInfo.LastKillValid = true; 1210 } 1211 1212 // At this point, we should have corrected last kill and LowerBound to be 1213 // in bounds. 1214 assert(LocInfo.LowerBound < VersionStack.size() && 1215 "Lower bound out of range"); 1216 assert(LocInfo.LastKill < VersionStack.size() && 1217 "Last kill info out of range"); 1218 // In any case, the new upper bound is the top of the stack. 1219 unsigned long UpperBound = VersionStack.size() - 1; 1220 1221 if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) { 1222 DEBUG(dbgs() << "MemorySSA skipping optimization of " << *MU << " (" 1223 << *(MU->getMemoryInst()) << ")" 1224 << " because there are " << UpperBound - LocInfo.LowerBound 1225 << " stores to disambiguate\n"); 1226 // Because we did not walk, LastKill is no longer valid, as this may 1227 // have been a kill. 1228 LocInfo.LastKillValid = false; 1229 continue; 1230 } 1231 bool FoundClobberResult = false; 1232 while (UpperBound > LocInfo.LowerBound) { 1233 if (isa<MemoryPhi>(VersionStack[UpperBound])) { 1234 // For phis, use the walker, see where we ended up, go there 1235 Instruction *UseInst = MU->getMemoryInst(); 1236 MemoryAccess *Result = Walker->getClobberingMemoryAccess(UseInst); 1237 // We are guaranteed to find it or something is wrong 1238 while (VersionStack[UpperBound] != Result) { 1239 assert(UpperBound != 0); 1240 --UpperBound; 1241 } 1242 FoundClobberResult = true; 1243 break; 1244 } 1245 1246 MemoryDef *MD = cast<MemoryDef>(VersionStack[UpperBound]); 1247 // If the lifetime of the pointer ends at this instruction, it's live on 1248 // entry. 1249 if (!UseMLOC.IsCall && lifetimeEndsAt(MD, UseMLOC.getLoc(), *AA)) { 1250 // Reset UpperBound to liveOnEntryDef's place in the stack 1251 UpperBound = 0; 1252 FoundClobberResult = true; 1253 break; 1254 } 1255 if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) { 1256 FoundClobberResult = true; 1257 break; 1258 } 1259 --UpperBound; 1260 } 1261 // At the end of this loop, UpperBound is either a clobber, or lower bound 1262 // PHI walking may cause it to be < LowerBound, and in fact, < LastKill. 1263 if (FoundClobberResult || UpperBound < LocInfo.LastKill) { 1264 MU->setDefiningAccess(VersionStack[UpperBound], true); 1265 // We were last killed now by where we got to 1266 LocInfo.LastKill = UpperBound; 1267 } else { 1268 // Otherwise, we checked all the new ones, and now we know we can get to 1269 // LastKill. 1270 MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true); 1271 } 1272 LocInfo.LowerBound = VersionStack.size() - 1; 1273 LocInfo.LowerBoundBlock = BB; 1274 } 1275} 1276 1277/// Optimize uses to point to their actual clobbering definitions. 1278void MemorySSA::OptimizeUses::optimizeUses() { 1279 SmallVector<MemoryAccess *, 16> VersionStack; 1280 DenseMap<MemoryLocOrCall, MemlocStackInfo> LocStackInfo; 1281 VersionStack.push_back(MSSA->getLiveOnEntryDef()); 1282 1283 unsigned long StackEpoch = 1; 1284 unsigned long PopEpoch = 1; 1285 // We perform a non-recursive top-down dominator tree walk. 1286 for (const auto *DomNode : depth_first(DT->getRootNode())) 1287 optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack, 1288 LocStackInfo); 1289} 1290 1291void MemorySSA::placePHINodes( 1292 const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks, 1293 const DenseMap<const BasicBlock *, unsigned int> &BBNumbers) { 1294 // Determine where our MemoryPhi's should go 1295 ForwardIDFCalculator IDFs(*DT); 1296 IDFs.setDefiningBlocks(DefiningBlocks); 1297 SmallVector<BasicBlock *, 32> IDFBlocks; 1298 IDFs.calculate(IDFBlocks); 1299 1300 std::sort(IDFBlocks.begin(), IDFBlocks.end(), 1301 [&BBNumbers](const BasicBlock *A, const BasicBlock *B) { 1302 return BBNumbers.lookup(A) < BBNumbers.lookup(B); 1303 }); 1304 1305 // Now place MemoryPhi nodes. 1306 for (auto &BB : IDFBlocks) 1307 createMemoryPhi(BB); 1308} 1309 1310void MemorySSA::buildMemorySSA() { 1311 // We create an access to represent "live on entry", for things like 1312 // arguments or users of globals, where the memory they use is defined before 1313 // the beginning of the function. We do not actually insert it into the IR. 1314 // We do not define a live on exit for the immediate uses, and thus our 1315 // semantics do *not* imply that something with no immediate uses can simply 1316 // be removed. 1317 BasicBlock &StartingPoint = F.getEntryBlock(); 1318 LiveOnEntryDef = 1319 llvm::make_unique<MemoryDef>(F.getContext(), nullptr, nullptr, 1320 &StartingPoint, NextID++); 1321 DenseMap<const BasicBlock *, unsigned int> BBNumbers; 1322 unsigned NextBBNum = 0; 1323 1324 // We maintain lists of memory accesses per-block, trading memory for time. We 1325 // could just look up the memory access for every possible instruction in the 1326 // stream. 1327 SmallPtrSet<BasicBlock *, 32> DefiningBlocks; 1328 // Go through each block, figure out where defs occur, and chain together all 1329 // the accesses. 1330 for (BasicBlock &B : F) { 1331 BBNumbers[&B] = NextBBNum++; 1332 bool InsertIntoDef = false; 1333 AccessList *Accesses = nullptr; 1334 DefsList *Defs = nullptr; 1335 for (Instruction &I : B) { 1336 MemoryUseOrDef *MUD = createNewAccess(&I); 1337 if (!MUD) 1338 continue; 1339 1340 if (!Accesses) 1341 Accesses = getOrCreateAccessList(&B); 1342 Accesses->push_back(MUD); 1343 if (isa<MemoryDef>(MUD)) { 1344 InsertIntoDef = true; 1345 if (!Defs) 1346 Defs = getOrCreateDefsList(&B); 1347 Defs->push_back(*MUD); 1348 } 1349 } 1350 if (InsertIntoDef) 1351 DefiningBlocks.insert(&B); 1352 } 1353 placePHINodes(DefiningBlocks, BBNumbers); 1354 1355 // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get 1356 // filled in with all blocks. 1357 SmallPtrSet<BasicBlock *, 16> Visited; 1358 renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited); 1359 1360 CachingWalker *Walker = getWalkerImpl(); 1361 1362 // We're doing a batch of updates; don't drop useful caches between them. 1363 Walker->setAutoResetWalker(false); 1364 OptimizeUses(this, Walker, AA, DT).optimizeUses(); 1365 Walker->setAutoResetWalker(true); 1366 Walker->resetClobberWalker(); 1367 1368 // Mark the uses in unreachable blocks as live on entry, so that they go 1369 // somewhere. 1370 for (auto &BB : F) 1371 if (!Visited.count(&BB)) 1372 markUnreachableAsLiveOnEntry(&BB); 1373} 1374 1375MemorySSAWalker *MemorySSA::getWalker() { return getWalkerImpl(); } 1376 1377MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() { 1378 if (Walker) 1379 return Walker.get(); 1380 1381 Walker = llvm::make_unique<CachingWalker>(this, AA, DT); 1382 return Walker.get(); 1383} 1384 1385// This is a helper function used by the creation routines. It places NewAccess 1386// into the access and defs lists for a given basic block, at the given 1387// insertion point. 1388void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess, 1389 const BasicBlock *BB, 1390 InsertionPlace Point) { 1391 auto *Accesses = getOrCreateAccessList(BB); 1392 if (Point == Beginning) { 1393 // If it's a phi node, it goes first, otherwise, it goes after any phi 1394 // nodes. 1395 if (isa<MemoryPhi>(NewAccess)) { 1396 Accesses->push_front(NewAccess); 1397 auto *Defs = getOrCreateDefsList(BB); 1398 Defs->push_front(*NewAccess); 1399 } else { 1400 auto AI = find_if_not( 1401 *Accesses, [](const MemoryAccess &MA) { return isa<MemoryPhi>(MA); }); 1402 Accesses->insert(AI, NewAccess); 1403 if (!isa<MemoryUse>(NewAccess)) { 1404 auto *Defs = getOrCreateDefsList(BB); 1405 auto DI = find_if_not( 1406 *Defs, [](const MemoryAccess &MA) { return isa<MemoryPhi>(MA); }); 1407 Defs->insert(DI, *NewAccess); 1408 } 1409 } 1410 } else { 1411 Accesses->push_back(NewAccess); 1412 if (!isa<MemoryUse>(NewAccess)) { 1413 auto *Defs = getOrCreateDefsList(BB); 1414 Defs->push_back(*NewAccess); 1415 } 1416 } 1417 BlockNumberingValid.erase(BB); 1418} 1419 1420void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB, 1421 AccessList::iterator InsertPt) { 1422 auto *Accesses = getWritableBlockAccesses(BB); 1423 bool WasEnd = InsertPt == Accesses->end(); 1424 Accesses->insert(AccessList::iterator(InsertPt), What); 1425 if (!isa<MemoryUse>(What)) { 1426 auto *Defs = getOrCreateDefsList(BB); 1427 // If we got asked to insert at the end, we have an easy job, just shove it 1428 // at the end. If we got asked to insert before an existing def, we also get 1429 // an terator. If we got asked to insert before a use, we have to hunt for 1430 // the next def. 1431 if (WasEnd) { 1432 Defs->push_back(*What); 1433 } else if (isa<MemoryDef>(InsertPt)) { 1434 Defs->insert(InsertPt->getDefsIterator(), *What); 1435 } else { 1436 while (InsertPt != Accesses->end() && !isa<MemoryDef>(InsertPt)) 1437 ++InsertPt; 1438 // Either we found a def, or we are inserting at the end 1439 if (InsertPt == Accesses->end()) 1440 Defs->push_back(*What); 1441 else 1442 Defs->insert(InsertPt->getDefsIterator(), *What); 1443 } 1444 } 1445 BlockNumberingValid.erase(BB); 1446} 1447 1448// Move What before Where in the IR. The end result is taht What will belong to 1449// the right lists and have the right Block set, but will not otherwise be 1450// correct. It will not have the right defining access, and if it is a def, 1451// things below it will not properly be updated. 1452void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB, 1453 AccessList::iterator Where) { 1454 // Keep it in the lookup tables, remove from the lists 1455 removeFromLists(What, false); 1456 What->setBlock(BB); 1457 insertIntoListsBefore(What, BB, Where); 1458} 1459 1460void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB, 1461 InsertionPlace Point) { 1462 removeFromLists(What, false); 1463 What->setBlock(BB); 1464 insertIntoListsForBlock(What, BB, Point); 1465} 1466 1467MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) { 1468 assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB"); 1469 MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++); 1470 // Phi's always are placed at the front of the block. 1471 insertIntoListsForBlock(Phi, BB, Beginning); 1472 ValueToMemoryAccess[BB] = Phi; 1473 return Phi; 1474} 1475 1476MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I, 1477 MemoryAccess *Definition) { 1478 assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI"); 1479 MemoryUseOrDef *NewAccess = createNewAccess(I); 1480 assert( 1481 NewAccess != nullptr && 1482 "Tried to create a memory access for a non-memory touching instruction"); 1483 NewAccess->setDefiningAccess(Definition); 1484 return NewAccess; 1485} 1486 1487// Return true if the instruction has ordering constraints. 1488// Note specifically that this only considers stores and loads 1489// because others are still considered ModRef by getModRefInfo. 1490static inline bool isOrdered(const Instruction *I) { 1491 if (auto *SI = dyn_cast<StoreInst>(I)) { 1492 if (!SI->isUnordered()) 1493 return true; 1494 } else if (auto *LI = dyn_cast<LoadInst>(I)) { 1495 if (!LI->isUnordered()) 1496 return true; 1497 } 1498 return false; 1499} 1500 1501/// \brief Helper function to create new memory accesses 1502MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) { 1503 // The assume intrinsic has a control dependency which we model by claiming 1504 // that it writes arbitrarily. Ignore that fake memory dependency here. 1505 // FIXME: Replace this special casing with a more accurate modelling of 1506 // assume's control dependency. 1507 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 1508 if (II->getIntrinsicID() == Intrinsic::assume) 1509 return nullptr; 1510 1511 // Find out what affect this instruction has on memory. 1512 ModRefInfo ModRef = AA->getModRefInfo(I, None); 1513 // The isOrdered check is used to ensure that volatiles end up as defs 1514 // (atomics end up as ModRef right now anyway). Until we separate the 1515 // ordering chain from the memory chain, this enables people to see at least 1516 // some relative ordering to volatiles. Note that getClobberingMemoryAccess 1517 // will still give an answer that bypasses other volatile loads. TODO: 1518 // Separate memory aliasing and ordering into two different chains so that we 1519 // can precisely represent both "what memory will this read/write/is clobbered 1520 // by" and "what instructions can I move this past". 1521 bool Def = isModSet(ModRef) || isOrdered(I); 1522 bool Use = isRefSet(ModRef); 1523 1524 // It's possible for an instruction to not modify memory at all. During 1525 // construction, we ignore them. 1526 if (!Def && !Use) 1527 return nullptr; 1528 1529 assert((Def || Use) && 1530 "Trying to create a memory access with a non-memory instruction"); 1531 1532 MemoryUseOrDef *MUD; 1533 if (Def) 1534 MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++); 1535 else 1536 MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent()); 1537 ValueToMemoryAccess[I] = MUD; 1538 return MUD; 1539} 1540 1541/// \brief Returns true if \p Replacer dominates \p Replacee . 1542bool MemorySSA::dominatesUse(const MemoryAccess *Replacer, 1543 const MemoryAccess *Replacee) const { 1544 if (isa<MemoryUseOrDef>(Replacee)) 1545 return DT->dominates(Replacer->getBlock(), Replacee->getBlock()); 1546 const auto *MP = cast<MemoryPhi>(Replacee); 1547 // For a phi node, the use occurs in the predecessor block of the phi node. 1548 // Since we may occur multiple times in the phi node, we have to check each 1549 // operand to ensure Replacer dominates each operand where Replacee occurs. 1550 for (const Use &Arg : MP->operands()) { 1551 if (Arg.get() != Replacee && 1552 !DT->dominates(Replacer->getBlock(), MP->getIncomingBlock(Arg))) 1553 return false; 1554 } 1555 return true; 1556} 1557 1558/// \brief Properly remove \p MA from all of MemorySSA's lookup tables. 1559void MemorySSA::removeFromLookups(MemoryAccess *MA) { 1560 assert(MA->use_empty() && 1561 "Trying to remove memory access that still has uses"); 1562 BlockNumbering.erase(MA); 1563 if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) 1564 MUD->setDefiningAccess(nullptr); 1565 // Invalidate our walker's cache if necessary 1566 if (!isa<MemoryUse>(MA)) 1567 Walker->invalidateInfo(MA); 1568 // The call below to erase will destroy MA, so we can't change the order we 1569 // are doing things here 1570 Value *MemoryInst; 1571 if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) { 1572 MemoryInst = MUD->getMemoryInst(); 1573 } else { 1574 MemoryInst = MA->getBlock(); 1575 } 1576 auto VMA = ValueToMemoryAccess.find(MemoryInst); 1577 if (VMA->second == MA) 1578 ValueToMemoryAccess.erase(VMA); 1579} 1580 1581/// \brief Properly remove \p MA from all of MemorySSA's lists. 1582/// 1583/// Because of the way the intrusive list and use lists work, it is important to 1584/// do removal in the right order. 1585/// ShouldDelete defaults to true, and will cause the memory access to also be 1586/// deleted, not just removed. 1587void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) { 1588 // The access list owns the reference, so we erase it from the non-owning list 1589 // first. 1590 if (!isa<MemoryUse>(MA)) { 1591 auto DefsIt = PerBlockDefs.find(MA->getBlock()); 1592 std::unique_ptr<DefsList> &Defs = DefsIt->second; 1593 Defs->remove(*MA); 1594 if (Defs->empty()) 1595 PerBlockDefs.erase(DefsIt); 1596 } 1597 1598 // The erase call here will delete it. If we don't want it deleted, we call 1599 // remove instead. 1600 auto AccessIt = PerBlockAccesses.find(MA->getBlock()); 1601 std::unique_ptr<AccessList> &Accesses = AccessIt->second; 1602 if (ShouldDelete) 1603 Accesses->erase(MA); 1604 else 1605 Accesses->remove(MA); 1606 1607 if (Accesses->empty()) 1608 PerBlockAccesses.erase(AccessIt); 1609} 1610 1611void MemorySSA::print(raw_ostream &OS) const { 1612 MemorySSAAnnotatedWriter Writer(this); 1613 F.print(OS, &Writer); 1614} 1615 1616#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1617LLVM_DUMP_METHOD void MemorySSA::dump() const { print(dbgs()); } 1618#endif 1619 1620void MemorySSA::verifyMemorySSA() const { 1621 verifyDefUses(F); 1622 verifyDomination(F); 1623 verifyOrdering(F); 1624 Walker->verify(this); 1625} 1626 1627/// \brief Verify that the order and existence of MemoryAccesses matches the 1628/// order and existence of memory affecting instructions. 1629void MemorySSA::verifyOrdering(Function &F) const { 1630 // Walk all the blocks, comparing what the lookups think and what the access 1631 // lists think, as well as the order in the blocks vs the order in the access 1632 // lists. 1633 SmallVector<MemoryAccess *, 32> ActualAccesses; 1634 SmallVector<MemoryAccess *, 32> ActualDefs; 1635 for (BasicBlock &B : F) { 1636 const AccessList *AL = getBlockAccesses(&B); 1637 const auto *DL = getBlockDefs(&B); 1638 MemoryAccess *Phi = getMemoryAccess(&B); 1639 if (Phi) { 1640 ActualAccesses.push_back(Phi); 1641 ActualDefs.push_back(Phi); 1642 } 1643 1644 for (Instruction &I : B) { 1645 MemoryAccess *MA = getMemoryAccess(&I); 1646 assert((!MA || (AL && (isa<MemoryUse>(MA) || DL))) && 1647 "We have memory affecting instructions " 1648 "in this block but they are not in the " 1649 "access list or defs list"); 1650 if (MA) { 1651 ActualAccesses.push_back(MA); 1652 if (isa<MemoryDef>(MA)) 1653 ActualDefs.push_back(MA); 1654 } 1655 } 1656 // Either we hit the assert, really have no accesses, or we have both 1657 // accesses and an access list. 1658 // Same with defs. 1659 if (!AL && !DL) 1660 continue; 1661 assert(AL->size() == ActualAccesses.size() && 1662 "We don't have the same number of accesses in the block as on the " 1663 "access list"); 1664 assert((DL || ActualDefs.size() == 0) && 1665 "Either we should have a defs list, or we should have no defs"); 1666 assert((!DL || DL->size() == ActualDefs.size()) && 1667 "We don't have the same number of defs in the block as on the " 1668 "def list"); 1669 auto ALI = AL->begin(); 1670 auto AAI = ActualAccesses.begin(); 1671 while (ALI != AL->end() && AAI != ActualAccesses.end()) { 1672 assert(&*ALI == *AAI && "Not the same accesses in the same order"); 1673 ++ALI; 1674 ++AAI; 1675 } 1676 ActualAccesses.clear(); 1677 if (DL) { 1678 auto DLI = DL->begin(); 1679 auto ADI = ActualDefs.begin(); 1680 while (DLI != DL->end() && ADI != ActualDefs.end()) { 1681 assert(&*DLI == *ADI && "Not the same defs in the same order"); 1682 ++DLI; 1683 ++ADI; 1684 } 1685 } 1686 ActualDefs.clear(); 1687 } 1688} 1689 1690/// \brief Verify the domination properties of MemorySSA by checking that each 1691/// definition dominates all of its uses. 1692void MemorySSA::verifyDomination(Function &F) const { 1693#ifndef NDEBUG 1694 for (BasicBlock &B : F) { 1695 // Phi nodes are attached to basic blocks 1696 if (MemoryPhi *MP = getMemoryAccess(&B)) 1697 for (const Use &U : MP->uses()) 1698 assert(dominates(MP, U) && "Memory PHI does not dominate it's uses"); 1699 1700 for (Instruction &I : B) { 1701 MemoryAccess *MD = dyn_cast_or_null<MemoryDef>(getMemoryAccess(&I)); 1702 if (!MD) 1703 continue; 1704 1705 for (const Use &U : MD->uses()) 1706 assert(dominates(MD, U) && "Memory Def does not dominate it's uses"); 1707 } 1708 } 1709#endif 1710} 1711 1712/// \brief Verify the def-use lists in MemorySSA, by verifying that \p Use 1713/// appears in the use list of \p Def. 1714void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const { 1715#ifndef NDEBUG 1716 // The live on entry use may cause us to get a NULL def here 1717 if (!Def) 1718 assert(isLiveOnEntryDef(Use) && 1719 "Null def but use not point to live on entry def"); 1720 else 1721 assert(is_contained(Def->users(), Use) && 1722 "Did not find use in def's use list"); 1723#endif 1724} 1725 1726/// \brief Verify the immediate use information, by walking all the memory 1727/// accesses and verifying that, for each use, it appears in the 1728/// appropriate def's use list 1729void MemorySSA::verifyDefUses(Function &F) const { 1730 for (BasicBlock &B : F) { 1731 // Phi nodes are attached to basic blocks 1732 if (MemoryPhi *Phi = getMemoryAccess(&B)) { 1733 assert(Phi->getNumOperands() == static_cast<unsigned>(std::distance( 1734 pred_begin(&B), pred_end(&B))) && 1735 "Incomplete MemoryPhi Node"); 1736 for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) 1737 verifyUseInDefs(Phi->getIncomingValue(I), Phi); 1738 } 1739 1740 for (Instruction &I : B) { 1741 if (MemoryUseOrDef *MA = getMemoryAccess(&I)) { 1742 verifyUseInDefs(MA->getDefiningAccess(), MA); 1743 } 1744 } 1745 } 1746} 1747 1748MemoryUseOrDef *MemorySSA::getMemoryAccess(const Instruction *I) const { 1749 return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I)); 1750} 1751 1752MemoryPhi *MemorySSA::getMemoryAccess(const BasicBlock *BB) const { 1753 return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB))); 1754} 1755 1756/// Perform a local numbering on blocks so that instruction ordering can be 1757/// determined in constant time. 1758/// TODO: We currently just number in order. If we numbered by N, we could 1759/// allow at least N-1 sequences of insertBefore or insertAfter (and at least 1760/// log2(N) sequences of mixed before and after) without needing to invalidate 1761/// the numbering. 1762void MemorySSA::renumberBlock(const BasicBlock *B) const { 1763 // The pre-increment ensures the numbers really start at 1. 1764 unsigned long CurrentNumber = 0; 1765 const AccessList *AL = getBlockAccesses(B); 1766 assert(AL != nullptr && "Asking to renumber an empty block"); 1767 for (const auto &I : *AL) 1768 BlockNumbering[&I] = ++CurrentNumber; 1769 BlockNumberingValid.insert(B); 1770} 1771 1772/// \brief Determine, for two memory accesses in the same block, 1773/// whether \p Dominator dominates \p Dominatee. 1774/// \returns True if \p Dominator dominates \p Dominatee. 1775bool MemorySSA::locallyDominates(const MemoryAccess *Dominator, 1776 const MemoryAccess *Dominatee) const { 1777 const BasicBlock *DominatorBlock = Dominator->getBlock(); 1778 1779 assert((DominatorBlock == Dominatee->getBlock()) && 1780 "Asking for local domination when accesses are in different blocks!"); 1781 // A node dominates itself. 1782 if (Dominatee == Dominator) 1783 return true; 1784 1785 // When Dominatee is defined on function entry, it is not dominated by another 1786 // memory access. 1787 if (isLiveOnEntryDef(Dominatee)) 1788 return false; 1789 1790 // When Dominator is defined on function entry, it dominates the other memory 1791 // access. 1792 if (isLiveOnEntryDef(Dominator)) 1793 return true; 1794 1795 if (!BlockNumberingValid.count(DominatorBlock)) 1796 renumberBlock(DominatorBlock); 1797 1798 unsigned long DominatorNum = BlockNumbering.lookup(Dominator); 1799 // All numbers start with 1 1800 assert(DominatorNum != 0 && "Block was not numbered properly"); 1801 unsigned long DominateeNum = BlockNumbering.lookup(Dominatee); 1802 assert(DominateeNum != 0 && "Block was not numbered properly"); 1803 return DominatorNum < DominateeNum; 1804} 1805 1806bool MemorySSA::dominates(const MemoryAccess *Dominator, 1807 const MemoryAccess *Dominatee) const { 1808 if (Dominator == Dominatee) 1809 return true; 1810 1811 if (isLiveOnEntryDef(Dominatee)) 1812 return false; 1813 1814 if (Dominator->getBlock() != Dominatee->getBlock()) 1815 return DT->dominates(Dominator->getBlock(), Dominatee->getBlock()); 1816 return locallyDominates(Dominator, Dominatee); 1817} 1818 1819bool MemorySSA::dominates(const MemoryAccess *Dominator, 1820 const Use &Dominatee) const { 1821 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Dominatee.getUser())) { 1822 BasicBlock *UseBB = MP->getIncomingBlock(Dominatee); 1823 // The def must dominate the incoming block of the phi. 1824 if (UseBB != Dominator->getBlock()) 1825 return DT->dominates(Dominator->getBlock(), UseBB); 1826 // If the UseBB and the DefBB are the same, compare locally. 1827 return locallyDominates(Dominator, cast<MemoryAccess>(Dominatee)); 1828 } 1829 // If it's not a PHI node use, the normal dominates can already handle it. 1830 return dominates(Dominator, cast<MemoryAccess>(Dominatee.getUser())); 1831} 1832 1833const static char LiveOnEntryStr[] = "liveOnEntry"; 1834 1835void MemoryAccess::print(raw_ostream &OS) const { 1836 switch (getValueID()) { 1837 case MemoryPhiVal: return static_cast<const MemoryPhi *>(this)->print(OS); 1838 case MemoryDefVal: return static_cast<const MemoryDef *>(this)->print(OS); 1839 case MemoryUseVal: return static_cast<const MemoryUse *>(this)->print(OS); 1840 } 1841 llvm_unreachable("invalid value id"); 1842} 1843 1844void MemoryDef::print(raw_ostream &OS) const { 1845 MemoryAccess *UO = getDefiningAccess(); 1846 1847 OS << getID() << " = MemoryDef("; 1848 if (UO && UO->getID()) 1849 OS << UO->getID(); 1850 else 1851 OS << LiveOnEntryStr; 1852 OS << ')'; 1853} 1854 1855void MemoryPhi::print(raw_ostream &OS) const { 1856 bool First = true; 1857 OS << getID() << " = MemoryPhi("; 1858 for (const auto &Op : operands()) { 1859 BasicBlock *BB = getIncomingBlock(Op); 1860 MemoryAccess *MA = cast<MemoryAccess>(Op); 1861 if (!First) 1862 OS << ','; 1863 else 1864 First = false; 1865 1866 OS << '{'; 1867 if (BB->hasName()) 1868 OS << BB->getName(); 1869 else 1870 BB->printAsOperand(OS, false); 1871 OS << ','; 1872 if (unsigned ID = MA->getID()) 1873 OS << ID; 1874 else 1875 OS << LiveOnEntryStr; 1876 OS << '}'; 1877 } 1878 OS << ')'; 1879} 1880 1881void MemoryUse::print(raw_ostream &OS) const { 1882 MemoryAccess *UO = getDefiningAccess(); 1883 OS << "MemoryUse("; 1884 if (UO && UO->getID()) 1885 OS << UO->getID(); 1886 else 1887 OS << LiveOnEntryStr; 1888 OS << ')'; 1889} 1890 1891void MemoryAccess::dump() const { 1892// Cannot completely remove virtual function even in release mode. 1893#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1894 print(dbgs()); 1895 dbgs() << "\n"; 1896#endif 1897} 1898 1899char MemorySSAPrinterLegacyPass::ID = 0; 1900 1901MemorySSAPrinterLegacyPass::MemorySSAPrinterLegacyPass() : FunctionPass(ID) { 1902 initializeMemorySSAPrinterLegacyPassPass(*PassRegistry::getPassRegistry()); 1903} 1904 1905void MemorySSAPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { 1906 AU.setPreservesAll(); 1907 AU.addRequired<MemorySSAWrapperPass>(); 1908} 1909 1910bool MemorySSAPrinterLegacyPass::runOnFunction(Function &F) { 1911 auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA(); 1912 MSSA.print(dbgs()); 1913 if (VerifyMemorySSA) 1914 MSSA.verifyMemorySSA(); 1915 return false; 1916} 1917 1918AnalysisKey MemorySSAAnalysis::Key; 1919 1920MemorySSAAnalysis::Result MemorySSAAnalysis::run(Function &F, 1921 FunctionAnalysisManager &AM) { 1922 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 1923 auto &AA = AM.getResult<AAManager>(F); 1924 return MemorySSAAnalysis::Result(llvm::make_unique<MemorySSA>(F, &AA, &DT)); 1925} 1926 1927PreservedAnalyses MemorySSAPrinterPass::run(Function &F, 1928 FunctionAnalysisManager &AM) { 1929 OS << "MemorySSA for function: " << F.getName() << "\n"; 1930 AM.getResult<MemorySSAAnalysis>(F).getMSSA().print(OS); 1931 1932 return PreservedAnalyses::all(); 1933} 1934 1935PreservedAnalyses MemorySSAVerifierPass::run(Function &F, 1936 FunctionAnalysisManager &AM) { 1937 AM.getResult<MemorySSAAnalysis>(F).getMSSA().verifyMemorySSA(); 1938 1939 return PreservedAnalyses::all(); 1940} 1941 1942char MemorySSAWrapperPass::ID = 0; 1943 1944MemorySSAWrapperPass::MemorySSAWrapperPass() : FunctionPass(ID) { 1945 initializeMemorySSAWrapperPassPass(*PassRegistry::getPassRegistry()); 1946} 1947 1948void MemorySSAWrapperPass::releaseMemory() { MSSA.reset(); } 1949 1950void MemorySSAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 1951 AU.setPreservesAll(); 1952 AU.addRequiredTransitive<DominatorTreeWrapperPass>(); 1953 AU.addRequiredTransitive<AAResultsWrapperPass>(); 1954} 1955 1956bool MemorySSAWrapperPass::runOnFunction(Function &F) { 1957 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1958 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); 1959 MSSA.reset(new MemorySSA(F, &AA, &DT)); 1960 return false; 1961} 1962 1963void MemorySSAWrapperPass::verifyAnalysis() const { MSSA->verifyMemorySSA(); } 1964 1965void MemorySSAWrapperPass::print(raw_ostream &OS, const Module *M) const { 1966 MSSA->print(OS); 1967} 1968 1969MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {} 1970 1971MemorySSA::CachingWalker::CachingWalker(MemorySSA *M, AliasAnalysis *A, 1972 DominatorTree *D) 1973 : MemorySSAWalker(M), Walker(*M, *A, *D) {} 1974 1975void MemorySSA::CachingWalker::invalidateInfo(MemoryAccess *MA) { 1976 if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) 1977 MUD->resetOptimized(); 1978} 1979 1980/// \brief Walk the use-def chains starting at \p MA and find 1981/// the MemoryAccess that actually clobbers Loc. 1982/// 1983/// \returns our clobbering memory access 1984MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess( 1985 MemoryAccess *StartingAccess, UpwardsMemoryQuery &Q) { 1986 MemoryAccess *New = Walker.findClobber(StartingAccess, Q); 1987#ifdef EXPENSIVE_CHECKS 1988 MemoryAccess *NewNoCache = Walker.findClobber(StartingAccess, Q); 1989 assert(NewNoCache == New && "Cache made us hand back a different result?"); 1990 (void)NewNoCache; 1991#endif 1992 if (AutoResetWalker) 1993 resetClobberWalker(); 1994 return New; 1995} 1996 1997MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess( 1998 MemoryAccess *StartingAccess, const MemoryLocation &Loc) { 1999 if (isa<MemoryPhi>(StartingAccess)) 2000 return StartingAccess; 2001 2002 auto *StartingUseOrDef = cast<MemoryUseOrDef>(StartingAccess); 2003 if (MSSA->isLiveOnEntryDef(StartingUseOrDef)) 2004 return StartingUseOrDef; 2005 2006 Instruction *I = StartingUseOrDef->getMemoryInst(); 2007 2008 // Conservatively, fences are always clobbers, so don't perform the walk if we 2009 // hit a fence. 2010 if (!ImmutableCallSite(I) && I->isFenceLike()) 2011 return StartingUseOrDef; 2012 2013 UpwardsMemoryQuery Q; 2014 Q.OriginalAccess = StartingUseOrDef; 2015 Q.StartingLoc = Loc; 2016 Q.Inst = I; 2017 Q.IsCall = false; 2018 2019 // Unlike the other function, do not walk to the def of a def, because we are 2020 // handed something we already believe is the clobbering access. 2021 MemoryAccess *DefiningAccess = isa<MemoryUse>(StartingUseOrDef) 2022 ? StartingUseOrDef->getDefiningAccess() 2023 : StartingUseOrDef; 2024 2025 MemoryAccess *Clobber = getClobberingMemoryAccess(DefiningAccess, Q); 2026 DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is "); 2027 DEBUG(dbgs() << *StartingUseOrDef << "\n"); 2028 DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is "); 2029 DEBUG(dbgs() << *Clobber << "\n"); 2030 return Clobber; 2031} 2032 2033MemoryAccess * 2034MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) { 2035 auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA); 2036 // If this is a MemoryPhi, we can't do anything. 2037 if (!StartingAccess) 2038 return MA; 2039 2040 // If this is an already optimized use or def, return the optimized result. 2041 // Note: Currently, we do not store the optimized def result because we'd need 2042 // a separate field, since we can't use it as the defining access. 2043 if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) 2044 if (MUD->isOptimized()) 2045 return MUD->getOptimized(); 2046 2047 const Instruction *I = StartingAccess->getMemoryInst(); 2048 UpwardsMemoryQuery Q(I, StartingAccess); 2049 // We can't sanely do anything with a fences, they conservatively 2050 // clobber all memory, and have no locations to get pointers from to 2051 // try to disambiguate. 2052 if (!Q.IsCall && I->isFenceLike()) 2053 return StartingAccess; 2054 2055 if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) { 2056 MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef(); 2057 if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) 2058 MUD->setOptimized(LiveOnEntry); 2059 return LiveOnEntry; 2060 } 2061 2062 // Start with the thing we already think clobbers this location 2063 MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess(); 2064 2065 // At this point, DefiningAccess may be the live on entry def. 2066 // If it is, we will not get a better result. 2067 if (MSSA->isLiveOnEntryDef(DefiningAccess)) 2068 return DefiningAccess; 2069 2070 MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q); 2071 DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is "); 2072 DEBUG(dbgs() << *DefiningAccess << "\n"); 2073 DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is "); 2074 DEBUG(dbgs() << *Result << "\n"); 2075 if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) 2076 MUD->setOptimized(Result); 2077 2078 return Result; 2079} 2080 2081MemoryAccess * 2082DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA) { 2083 if (auto *Use = dyn_cast<MemoryUseOrDef>(MA)) 2084 return Use->getDefiningAccess(); 2085 return MA; 2086} 2087 2088MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess( 2089 MemoryAccess *StartingAccess, const MemoryLocation &) { 2090 if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess)) 2091 return Use->getDefiningAccess(); 2092 return StartingAccess; 2093} 2094 2095void MemoryPhi::deleteMe(DerivedUser *Self) { 2096 delete static_cast<MemoryPhi *>(Self); 2097} 2098 2099void MemoryDef::deleteMe(DerivedUser *Self) { 2100 delete static_cast<MemoryDef *>(Self); 2101} 2102 2103void MemoryUse::deleteMe(DerivedUser *Self) { 2104 delete static_cast<MemoryUse *>(Self); 2105} 2106