1 //===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===// 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 /// \file 10 /// This file exposes an interface to building/using memory SSA to 11 /// walk memory instructions using a use/def graph. 12 /// 13 /// Memory SSA class builds an SSA form that links together memory access 14 /// instructions such as loads, stores, atomics, and calls. Additionally, it 15 /// does a trivial form of "heap versioning" Every time the memory state changes 16 /// in the program, we generate a new heap version. It generates 17 /// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions. 18 /// 19 /// As a trivial example, 20 /// define i32 @main() #0 { 21 /// entry: 22 /// %call = call noalias i8* @_Znwm(i64 4) #2 23 /// %0 = bitcast i8* %call to i32* 24 /// %call1 = call noalias i8* @_Znwm(i64 4) #2 25 /// %1 = bitcast i8* %call1 to i32* 26 /// store i32 5, i32* %0, align 4 27 /// store i32 7, i32* %1, align 4 28 /// %2 = load i32* %0, align 4 29 /// %3 = load i32* %1, align 4 30 /// %add = add nsw i32 %2, %3 31 /// ret i32 %add 32 /// } 33 /// 34 /// Will become 35 /// define i32 @main() #0 { 36 /// entry: 37 /// ; 1 = MemoryDef(0) 38 /// %call = call noalias i8* @_Znwm(i64 4) #3 39 /// %2 = bitcast i8* %call to i32* 40 /// ; 2 = MemoryDef(1) 41 /// %call1 = call noalias i8* @_Znwm(i64 4) #3 42 /// %4 = bitcast i8* %call1 to i32* 43 /// ; 3 = MemoryDef(2) 44 /// store i32 5, i32* %2, align 4 45 /// ; 4 = MemoryDef(3) 46 /// store i32 7, i32* %4, align 4 47 /// ; MemoryUse(3) 48 /// %7 = load i32* %2, align 4 49 /// ; MemoryUse(4) 50 /// %8 = load i32* %4, align 4 51 /// %add = add nsw i32 %7, %8 52 /// ret i32 %add 53 /// } 54 /// 55 /// Given this form, all the stores that could ever effect the load at %8 can be 56 /// gotten by using the MemoryUse associated with it, and walking from use to 57 /// def until you hit the top of the function. 58 /// 59 /// Each def also has a list of users associated with it, so you can walk from 60 /// both def to users, and users to defs. Note that we disambiguate MemoryUses, 61 /// but not the RHS of MemoryDefs. You can see this above at %7, which would 62 /// otherwise be a MemoryUse(4). Being disambiguated means that for a given 63 /// store, all the MemoryUses on its use lists are may-aliases of that store 64 /// (but the MemoryDefs on its use list may not be). 65 /// 66 /// MemoryDefs are not disambiguated because it would require multiple reaching 67 /// definitions, which would require multiple phis, and multiple memoryaccesses 68 /// per instruction. 69 // 70 //===----------------------------------------------------------------------===// 71 72 #ifndef LLVM_ANALYSIS_MEMORYSSA_H 73 #define LLVM_ANALYSIS_MEMORYSSA_H 74 75 #include "llvm/ADT/DenseMap.h" 76 #include "llvm/ADT/GraphTraits.h" 77 #include "llvm/ADT/SmallPtrSet.h" 78 #include "llvm/ADT/SmallVector.h" 79 #include "llvm/ADT/ilist.h" 80 #include "llvm/ADT/ilist_node.h" 81 #include "llvm/ADT/iterator.h" 82 #include "llvm/ADT/iterator_range.h" 83 #include "llvm/ADT/simple_ilist.h" 84 #include "llvm/Analysis/AliasAnalysis.h" 85 #include "llvm/Analysis/MemoryLocation.h" 86 #include "llvm/Analysis/PHITransAddr.h" 87 #include "llvm/IR/BasicBlock.h" 88 #include "llvm/IR/DerivedUser.h" 89 #include "llvm/IR/Dominators.h" 90 #include "llvm/IR/Module.h" 91 #include "llvm/IR/Operator.h" 92 #include "llvm/IR/Type.h" 93 #include "llvm/IR/Use.h" 94 #include "llvm/IR/User.h" 95 #include "llvm/IR/Value.h" 96 #include "llvm/IR/ValueHandle.h" 97 #include "llvm/Pass.h" 98 #include "llvm/Support/Casting.h" 99 #include "llvm/Support/CommandLine.h" 100 #include <algorithm> 101 #include <cassert> 102 #include <cstddef> 103 #include <iterator> 104 #include <memory> 105 #include <utility> 106 107 namespace llvm { 108 109 /// Enables memory ssa as a dependency for loop passes. 110 extern cl::opt<bool> EnableMSSALoopDependency; 111 112 class AllocaInst; 113 class Function; 114 class Instruction; 115 class MemoryAccess; 116 class MemorySSAWalker; 117 class LLVMContext; 118 class raw_ostream; 119 120 namespace MSSAHelpers { 121 122 struct AllAccessTag {}; 123 struct DefsOnlyTag {}; 124 125 } // end namespace MSSAHelpers 126 127 enum : unsigned { 128 // Used to signify what the default invalid ID is for MemoryAccess's 129 // getID() 130 INVALID_MEMORYACCESS_ID = -1U 131 }; 132 133 template <class T> class memoryaccess_def_iterator_base; 134 using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>; 135 using const_memoryaccess_def_iterator = 136 memoryaccess_def_iterator_base<const MemoryAccess>; 137 138 // The base for all memory accesses. All memory accesses in a block are 139 // linked together using an intrusive list. 140 class MemoryAccess 141 : public DerivedUser, 142 public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>, 143 public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> { 144 public: 145 using AllAccessType = 146 ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>; 147 using DefsOnlyType = 148 ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>; 149 150 MemoryAccess(const MemoryAccess &) = delete; 151 MemoryAccess &operator=(const MemoryAccess &) = delete; 152 153 void *operator new(size_t) = delete; 154 155 // Methods for support type inquiry through isa, cast, and 156 // dyn_cast classof(const Value * V)157 static bool classof(const Value *V) { 158 unsigned ID = V->getValueID(); 159 return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal; 160 } 161 getBlock()162 BasicBlock *getBlock() const { return Block; } 163 164 void print(raw_ostream &OS) const; 165 void dump() const; 166 167 /// The user iterators for a memory access 168 using iterator = user_iterator; 169 using const_iterator = const_user_iterator; 170 171 /// This iterator walks over all of the defs in a given 172 /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For 173 /// MemoryUse/MemoryDef, this walks the defining access. 174 memoryaccess_def_iterator defs_begin(); 175 const_memoryaccess_def_iterator defs_begin() const; 176 memoryaccess_def_iterator defs_end(); 177 const_memoryaccess_def_iterator defs_end() const; 178 179 /// Get the iterators for the all access list and the defs only list 180 /// We default to the all access list. getIterator()181 AllAccessType::self_iterator getIterator() { 182 return this->AllAccessType::getIterator(); 183 } getIterator()184 AllAccessType::const_self_iterator getIterator() const { 185 return this->AllAccessType::getIterator(); 186 } getReverseIterator()187 AllAccessType::reverse_self_iterator getReverseIterator() { 188 return this->AllAccessType::getReverseIterator(); 189 } getReverseIterator()190 AllAccessType::const_reverse_self_iterator getReverseIterator() const { 191 return this->AllAccessType::getReverseIterator(); 192 } getDefsIterator()193 DefsOnlyType::self_iterator getDefsIterator() { 194 return this->DefsOnlyType::getIterator(); 195 } getDefsIterator()196 DefsOnlyType::const_self_iterator getDefsIterator() const { 197 return this->DefsOnlyType::getIterator(); 198 } getReverseDefsIterator()199 DefsOnlyType::reverse_self_iterator getReverseDefsIterator() { 200 return this->DefsOnlyType::getReverseIterator(); 201 } getReverseDefsIterator()202 DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const { 203 return this->DefsOnlyType::getReverseIterator(); 204 } 205 206 protected: 207 friend class MemoryDef; 208 friend class MemoryPhi; 209 friend class MemorySSA; 210 friend class MemoryUse; 211 friend class MemoryUseOrDef; 212 213 /// Used by MemorySSA to change the block of a MemoryAccess when it is 214 /// moved. setBlock(BasicBlock * BB)215 void setBlock(BasicBlock *BB) { Block = BB; } 216 217 /// Used for debugging and tracking things about MemoryAccesses. 218 /// Guaranteed unique among MemoryAccesses, no guarantees otherwise. 219 inline unsigned getID() const; 220 MemoryAccess(LLVMContext & C,unsigned Vty,DeleteValueTy DeleteValue,BasicBlock * BB,unsigned NumOperands)221 MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue, 222 BasicBlock *BB, unsigned NumOperands) 223 : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue), 224 Block(BB) {} 225 226 // Use deleteValue() to delete a generic MemoryAccess. 227 ~MemoryAccess() = default; 228 229 private: 230 BasicBlock *Block; 231 }; 232 233 template <> 234 struct ilist_alloc_traits<MemoryAccess> { 235 static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); } 236 }; 237 238 inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) { 239 MA.print(OS); 240 return OS; 241 } 242 243 /// Class that has the common methods + fields of memory uses/defs. It's 244 /// a little awkward to have, but there are many cases where we want either a 245 /// use or def, and there are many cases where uses are needed (defs aren't 246 /// acceptable), and vice-versa. 247 /// 248 /// This class should never be instantiated directly; make a MemoryUse or 249 /// MemoryDef instead. 250 class MemoryUseOrDef : public MemoryAccess { 251 public: 252 void *operator new(size_t) = delete; 253 254 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); 255 256 /// Get the instruction that this MemoryUse represents. 257 Instruction *getMemoryInst() const { return MemoryInstruction; } 258 259 /// Get the access that produces the memory state used by this Use. 260 MemoryAccess *getDefiningAccess() const { return getOperand(0); } 261 262 static bool classof(const Value *MA) { 263 return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal; 264 } 265 266 // Sadly, these have to be public because they are needed in some of the 267 // iterators. 268 inline bool isOptimized() const; 269 inline MemoryAccess *getOptimized() const; 270 inline void setOptimized(MemoryAccess *); 271 272 // Retrieve AliasResult type of the optimized access. Ideally this would be 273 // returned by the caching walker and may go away in the future. 274 Optional<AliasResult> getOptimizedAccessType() const { 275 return isOptimized() ? OptimizedAccessAlias : None; 276 } 277 278 /// Reset the ID of what this MemoryUse was optimized to, causing it to 279 /// be rewalked by the walker if necessary. 280 /// This really should only be called by tests. 281 inline void resetOptimized(); 282 283 protected: 284 friend class MemorySSA; 285 friend class MemorySSAUpdater; 286 287 MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty, 288 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB, 289 unsigned NumOperands) 290 : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands), 291 MemoryInstruction(MI), OptimizedAccessAlias(AliasResult::MayAlias) { 292 setDefiningAccess(DMA); 293 } 294 295 // Use deleteValue() to delete a generic MemoryUseOrDef. 296 ~MemoryUseOrDef() = default; 297 298 void setOptimizedAccessType(Optional<AliasResult> AR) { 299 OptimizedAccessAlias = AR; 300 } 301 302 void setDefiningAccess( 303 MemoryAccess *DMA, bool Optimized = false, 304 Optional<AliasResult> AR = AliasResult(AliasResult::MayAlias)) { 305 if (!Optimized) { 306 setOperand(0, DMA); 307 return; 308 } 309 setOptimized(DMA); 310 setOptimizedAccessType(AR); 311 } 312 313 private: 314 Instruction *MemoryInstruction; 315 Optional<AliasResult> OptimizedAccessAlias; 316 }; 317 318 /// Represents read-only accesses to memory 319 /// 320 /// In particular, the set of Instructions that will be represented by 321 /// MemoryUse's is exactly the set of Instructions for which 322 /// AliasAnalysis::getModRefInfo returns "Ref". 323 class MemoryUse final : public MemoryUseOrDef { 324 public: 325 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); 326 327 MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB) 328 : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB, 329 /*NumOperands=*/1) {} 330 331 // allocate space for exactly one operand 332 void *operator new(size_t S) { return User::operator new(S, 1); } 333 void operator delete(void *Ptr) { User::operator delete(Ptr); } 334 335 static bool classof(const Value *MA) { 336 return MA->getValueID() == MemoryUseVal; 337 } 338 339 void print(raw_ostream &OS) const; 340 341 void setOptimized(MemoryAccess *DMA) { 342 OptimizedID = DMA->getID(); 343 setOperand(0, DMA); 344 } 345 346 bool isOptimized() const { 347 return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID(); 348 } 349 350 MemoryAccess *getOptimized() const { 351 return getDefiningAccess(); 352 } 353 354 void resetOptimized() { 355 OptimizedID = INVALID_MEMORYACCESS_ID; 356 } 357 358 protected: 359 friend class MemorySSA; 360 361 private: 362 static void deleteMe(DerivedUser *Self); 363 364 unsigned OptimizedID = INVALID_MEMORYACCESS_ID; 365 }; 366 367 template <> 368 struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {}; 369 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess) 370 371 /// Represents a read-write access to memory, whether it is a must-alias, 372 /// or a may-alias. 373 /// 374 /// In particular, the set of Instructions that will be represented by 375 /// MemoryDef's is exactly the set of Instructions for which 376 /// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef". 377 /// Note that, in order to provide def-def chains, all defs also have a use 378 /// associated with them. This use points to the nearest reaching 379 /// MemoryDef/MemoryPhi. 380 class MemoryDef final : public MemoryUseOrDef { 381 public: 382 friend class MemorySSA; 383 384 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); 385 386 MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB, 387 unsigned Ver) 388 : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB, 389 /*NumOperands=*/2), 390 ID(Ver) {} 391 392 // allocate space for exactly two operands 393 void *operator new(size_t S) { return User::operator new(S, 2); } 394 void operator delete(void *Ptr) { User::operator delete(Ptr); } 395 396 static bool classof(const Value *MA) { 397 return MA->getValueID() == MemoryDefVal; 398 } 399 400 void setOptimized(MemoryAccess *MA) { 401 setOperand(1, MA); 402 OptimizedID = MA->getID(); 403 } 404 405 MemoryAccess *getOptimized() const { 406 return cast_or_null<MemoryAccess>(getOperand(1)); 407 } 408 409 bool isOptimized() const { 410 return getOptimized() && OptimizedID == getOptimized()->getID(); 411 } 412 413 void resetOptimized() { 414 OptimizedID = INVALID_MEMORYACCESS_ID; 415 setOperand(1, nullptr); 416 } 417 418 void print(raw_ostream &OS) const; 419 420 unsigned getID() const { return ID; } 421 422 private: 423 static void deleteMe(DerivedUser *Self); 424 425 const unsigned ID; 426 unsigned OptimizedID = INVALID_MEMORYACCESS_ID; 427 }; 428 429 template <> 430 struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {}; 431 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess) 432 433 template <> 434 struct OperandTraits<MemoryUseOrDef> { 435 static Use *op_begin(MemoryUseOrDef *MUD) { 436 if (auto *MU = dyn_cast<MemoryUse>(MUD)) 437 return OperandTraits<MemoryUse>::op_begin(MU); 438 return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD)); 439 } 440 441 static Use *op_end(MemoryUseOrDef *MUD) { 442 if (auto *MU = dyn_cast<MemoryUse>(MUD)) 443 return OperandTraits<MemoryUse>::op_end(MU); 444 return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD)); 445 } 446 447 static unsigned operands(const MemoryUseOrDef *MUD) { 448 if (const auto *MU = dyn_cast<MemoryUse>(MUD)) 449 return OperandTraits<MemoryUse>::operands(MU); 450 return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD)); 451 } 452 }; 453 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess) 454 455 /// Represents phi nodes for memory accesses. 456 /// 457 /// These have the same semantic as regular phi nodes, with the exception that 458 /// only one phi will ever exist in a given basic block. 459 /// Guaranteeing one phi per block means guaranteeing there is only ever one 460 /// valid reaching MemoryDef/MemoryPHI along each path to the phi node. 461 /// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or 462 /// a MemoryPhi's operands. 463 /// That is, given 464 /// if (a) { 465 /// store %a 466 /// store %b 467 /// } 468 /// it *must* be transformed into 469 /// if (a) { 470 /// 1 = MemoryDef(liveOnEntry) 471 /// store %a 472 /// 2 = MemoryDef(1) 473 /// store %b 474 /// } 475 /// and *not* 476 /// if (a) { 477 /// 1 = MemoryDef(liveOnEntry) 478 /// store %a 479 /// 2 = MemoryDef(liveOnEntry) 480 /// store %b 481 /// } 482 /// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the 483 /// end of the branch, and if there are not two phi nodes, one will be 484 /// disconnected completely from the SSA graph below that point. 485 /// Because MemoryUse's do not generate new definitions, they do not have this 486 /// issue. 487 class MemoryPhi final : public MemoryAccess { 488 // allocate space for exactly zero operands 489 void *operator new(size_t S) { return User::operator new(S); } 490 491 public: 492 void operator delete(void *Ptr) { User::operator delete(Ptr); } 493 494 /// Provide fast operand accessors 495 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); 496 497 MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0) 498 : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver), 499 ReservedSpace(NumPreds) { 500 allocHungoffUses(ReservedSpace); 501 } 502 503 // Block iterator interface. This provides access to the list of incoming 504 // basic blocks, which parallels the list of incoming values. 505 using block_iterator = BasicBlock **; 506 using const_block_iterator = BasicBlock *const *; 507 508 block_iterator block_begin() { 509 return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace); 510 } 511 512 const_block_iterator block_begin() const { 513 return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace); 514 } 515 516 block_iterator block_end() { return block_begin() + getNumOperands(); } 517 518 const_block_iterator block_end() const { 519 return block_begin() + getNumOperands(); 520 } 521 522 iterator_range<block_iterator> blocks() { 523 return make_range(block_begin(), block_end()); 524 } 525 526 iterator_range<const_block_iterator> blocks() const { 527 return make_range(block_begin(), block_end()); 528 } 529 530 op_range incoming_values() { return operands(); } 531 532 const_op_range incoming_values() const { return operands(); } 533 534 /// Return the number of incoming edges 535 unsigned getNumIncomingValues() const { return getNumOperands(); } 536 537 /// Return incoming value number x 538 MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); } 539 void setIncomingValue(unsigned I, MemoryAccess *V) { 540 assert(V && "PHI node got a null value!"); 541 setOperand(I, V); 542 } 543 544 static unsigned getOperandNumForIncomingValue(unsigned I) { return I; } 545 static unsigned getIncomingValueNumForOperand(unsigned I) { return I; } 546 547 /// Return incoming basic block number @p i. 548 BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; } 549 550 /// Return incoming basic block corresponding 551 /// to an operand of the PHI. 552 BasicBlock *getIncomingBlock(const Use &U) const { 553 assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?"); 554 return getIncomingBlock(unsigned(&U - op_begin())); 555 } 556 557 /// Return incoming basic block corresponding 558 /// to value use iterator. 559 BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const { 560 return getIncomingBlock(I.getUse()); 561 } 562 563 void setIncomingBlock(unsigned I, BasicBlock *BB) { 564 assert(BB && "PHI node got a null basic block!"); 565 block_begin()[I] = BB; 566 } 567 568 /// Add an incoming value to the end of the PHI list 569 void addIncoming(MemoryAccess *V, BasicBlock *BB) { 570 if (getNumOperands() == ReservedSpace) 571 growOperands(); // Get more space! 572 // Initialize some new operands. 573 setNumHungOffUseOperands(getNumOperands() + 1); 574 setIncomingValue(getNumOperands() - 1, V); 575 setIncomingBlock(getNumOperands() - 1, BB); 576 } 577 578 /// Return the first index of the specified basic 579 /// block in the value list for this PHI. Returns -1 if no instance. 580 int getBasicBlockIndex(const BasicBlock *BB) const { 581 for (unsigned I = 0, E = getNumOperands(); I != E; ++I) 582 if (block_begin()[I] == BB) 583 return I; 584 return -1; 585 } 586 587 MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const { 588 int Idx = getBasicBlockIndex(BB); 589 assert(Idx >= 0 && "Invalid basic block argument!"); 590 return getIncomingValue(Idx); 591 } 592 593 // After deleting incoming position I, the order of incoming may be changed. 594 void unorderedDeleteIncoming(unsigned I) { 595 unsigned E = getNumOperands(); 596 assert(I < E && "Cannot remove out of bounds Phi entry."); 597 // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi 598 // itself should be deleted. 599 assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with " 600 "at least 2 values."); 601 setIncomingValue(I, getIncomingValue(E - 1)); 602 setIncomingBlock(I, block_begin()[E - 1]); 603 setOperand(E - 1, nullptr); 604 block_begin()[E - 1] = nullptr; 605 setNumHungOffUseOperands(getNumOperands() - 1); 606 } 607 608 // After deleting entries that satisfy Pred, remaining entries may have 609 // changed order. 610 template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) { 611 for (unsigned I = 0, E = getNumOperands(); I != E; ++I) 612 if (Pred(getIncomingValue(I), getIncomingBlock(I))) { 613 unorderedDeleteIncoming(I); 614 E = getNumOperands(); 615 --I; 616 } 617 assert(getNumOperands() >= 1 && 618 "Cannot remove all incoming blocks in a MemoryPhi."); 619 } 620 621 // After deleting incoming block BB, the incoming blocks order may be changed. 622 void unorderedDeleteIncomingBlock(const BasicBlock *BB) { 623 unorderedDeleteIncomingIf( 624 [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; }); 625 } 626 627 // After deleting incoming memory access MA, the incoming accesses order may 628 // be changed. 629 void unorderedDeleteIncomingValue(const MemoryAccess *MA) { 630 unorderedDeleteIncomingIf( 631 [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; }); 632 } 633 634 static bool classof(const Value *V) { 635 return V->getValueID() == MemoryPhiVal; 636 } 637 638 void print(raw_ostream &OS) const; 639 640 unsigned getID() const { return ID; } 641 642 protected: 643 friend class MemorySSA; 644 645 /// this is more complicated than the generic 646 /// User::allocHungoffUses, because we have to allocate Uses for the incoming 647 /// values and pointers to the incoming blocks, all in one allocation. 648 void allocHungoffUses(unsigned N) { 649 User::allocHungoffUses(N, /* IsPhi */ true); 650 } 651 652 private: 653 // For debugging only 654 const unsigned ID; 655 unsigned ReservedSpace; 656 657 /// This grows the operand list in response to a push_back style of 658 /// operation. This grows the number of ops by 1.5 times. 659 void growOperands() { 660 unsigned E = getNumOperands(); 661 // 2 op PHI nodes are VERY common, so reserve at least enough for that. 662 ReservedSpace = std::max(E + E / 2, 2u); 663 growHungoffUses(ReservedSpace, /* IsPhi */ true); 664 } 665 666 static void deleteMe(DerivedUser *Self); 667 }; 668 669 inline unsigned MemoryAccess::getID() const { 670 assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) && 671 "only memory defs and phis have ids"); 672 if (const auto *MD = dyn_cast<MemoryDef>(this)) 673 return MD->getID(); 674 return cast<MemoryPhi>(this)->getID(); 675 } 676 677 inline bool MemoryUseOrDef::isOptimized() const { 678 if (const auto *MD = dyn_cast<MemoryDef>(this)) 679 return MD->isOptimized(); 680 return cast<MemoryUse>(this)->isOptimized(); 681 } 682 683 inline MemoryAccess *MemoryUseOrDef::getOptimized() const { 684 if (const auto *MD = dyn_cast<MemoryDef>(this)) 685 return MD->getOptimized(); 686 return cast<MemoryUse>(this)->getOptimized(); 687 } 688 689 inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) { 690 if (auto *MD = dyn_cast<MemoryDef>(this)) 691 MD->setOptimized(MA); 692 else 693 cast<MemoryUse>(this)->setOptimized(MA); 694 } 695 696 inline void MemoryUseOrDef::resetOptimized() { 697 if (auto *MD = dyn_cast<MemoryDef>(this)) 698 MD->resetOptimized(); 699 else 700 cast<MemoryUse>(this)->resetOptimized(); 701 } 702 703 template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {}; 704 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess) 705 706 /// Encapsulates MemorySSA, including all data associated with memory 707 /// accesses. 708 class MemorySSA { 709 public: 710 MemorySSA(Function &, AliasAnalysis *, DominatorTree *); 711 712 // MemorySSA must remain where it's constructed; Walkers it creates store 713 // pointers to it. 714 MemorySSA(MemorySSA &&) = delete; 715 716 ~MemorySSA(); 717 718 MemorySSAWalker *getWalker(); 719 MemorySSAWalker *getSkipSelfWalker(); 720 721 /// Given a memory Mod/Ref'ing instruction, get the MemorySSA 722 /// access associated with it. If passed a basic block gets the memory phi 723 /// node that exists for that block, if there is one. Otherwise, this will get 724 /// a MemoryUseOrDef. 725 MemoryUseOrDef *getMemoryAccess(const Instruction *I) const { 726 return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I)); 727 } 728 729 MemoryPhi *getMemoryAccess(const BasicBlock *BB) const { 730 return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB))); 731 } 732 733 DominatorTree &getDomTree() const { return *DT; } 734 735 void dump() const; 736 void print(raw_ostream &) const; 737 738 /// Return true if \p MA represents the live on entry value 739 /// 740 /// Loads and stores from pointer arguments and other global values may be 741 /// defined by memory operations that do not occur in the current function, so 742 /// they may be live on entry to the function. MemorySSA represents such 743 /// memory state by the live on entry definition, which is guaranteed to occur 744 /// before any other memory access in the function. 745 inline bool isLiveOnEntryDef(const MemoryAccess *MA) const { 746 return MA == LiveOnEntryDef.get(); 747 } 748 749 inline MemoryAccess *getLiveOnEntryDef() const { 750 return LiveOnEntryDef.get(); 751 } 752 753 // Sadly, iplists, by default, owns and deletes pointers added to the 754 // list. It's not currently possible to have two iplists for the same type, 755 // where one owns the pointers, and one does not. This is because the traits 756 // are per-type, not per-tag. If this ever changes, we should make the 757 // DefList an iplist. 758 using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>; 759 using DefsList = 760 simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>; 761 762 /// Return the list of MemoryAccess's for a given basic block. 763 /// 764 /// This list is not modifiable by the user. 765 const AccessList *getBlockAccesses(const BasicBlock *BB) const { 766 return getWritableBlockAccesses(BB); 767 } 768 769 /// Return the list of MemoryDef's and MemoryPhi's for a given basic 770 /// block. 771 /// 772 /// This list is not modifiable by the user. 773 const DefsList *getBlockDefs(const BasicBlock *BB) const { 774 return getWritableBlockDefs(BB); 775 } 776 777 /// Given two memory accesses in the same basic block, determine 778 /// whether MemoryAccess \p A dominates MemoryAccess \p B. 779 bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const; 780 781 /// Given two memory accesses in potentially different blocks, 782 /// determine whether MemoryAccess \p A dominates MemoryAccess \p B. 783 bool dominates(const MemoryAccess *A, const MemoryAccess *B) const; 784 785 /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A 786 /// dominates Use \p B. 787 bool dominates(const MemoryAccess *A, const Use &B) const; 788 789 /// Verify that MemorySSA is self consistent (IE definitions dominate 790 /// all uses, uses appear in the right places). This is used by unit tests. 791 void verifyMemorySSA() const; 792 793 /// Used in various insertion functions to specify whether we are talking 794 /// about the beginning or end of a block. 795 enum InsertionPlace { Beginning, End, BeforeTerminator }; 796 797 protected: 798 // Used by Memory SSA annotater, dumpers, and wrapper pass 799 friend class MemorySSAAnnotatedWriter; 800 friend class MemorySSAPrinterLegacyPass; 801 friend class MemorySSAUpdater; 802 803 void verifyOrderingDominationAndDefUses(Function &F) const; 804 void verifyDominationNumbers(const Function &F) const; 805 void verifyPrevDefInPhis(Function &F) const; 806 807 // This is used by the use optimizer and updater. 808 AccessList *getWritableBlockAccesses(const BasicBlock *BB) const { 809 auto It = PerBlockAccesses.find(BB); 810 return It == PerBlockAccesses.end() ? nullptr : It->second.get(); 811 } 812 813 // This is used by the use optimizer and updater. 814 DefsList *getWritableBlockDefs(const BasicBlock *BB) const { 815 auto It = PerBlockDefs.find(BB); 816 return It == PerBlockDefs.end() ? nullptr : It->second.get(); 817 } 818 819 // These is used by the updater to perform various internal MemorySSA 820 // machinsations. They do not always leave the IR in a correct state, and 821 // relies on the updater to fixup what it breaks, so it is not public. 822 823 void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where); 824 void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point); 825 826 // Rename the dominator tree branch rooted at BB. 827 void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, 828 SmallPtrSetImpl<BasicBlock *> &Visited) { 829 renamePass(DT->getNode(BB), IncomingVal, Visited, true, true); 830 } 831 832 void removeFromLookups(MemoryAccess *); 833 void removeFromLists(MemoryAccess *, bool ShouldDelete = true); 834 void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *, 835 InsertionPlace); 836 void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, 837 AccessList::iterator); 838 MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *, 839 const MemoryUseOrDef *Template = nullptr, 840 bool CreationMustSucceed = true); 841 842 private: 843 template <class AliasAnalysisType> class ClobberWalkerBase; 844 template <class AliasAnalysisType> class CachingWalker; 845 template <class AliasAnalysisType> class SkipSelfWalker; 846 class OptimizeUses; 847 848 CachingWalker<AliasAnalysis> *getWalkerImpl(); 849 void buildMemorySSA(BatchAAResults &BAA); 850 851 void prepareForMoveTo(MemoryAccess *, BasicBlock *); 852 void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const; 853 854 using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>; 855 using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>; 856 857 void markUnreachableAsLiveOnEntry(BasicBlock *BB); 858 MemoryPhi *createMemoryPhi(BasicBlock *BB); 859 template <typename AliasAnalysisType> 860 MemoryUseOrDef *createNewAccess(Instruction *, AliasAnalysisType *, 861 const MemoryUseOrDef *Template = nullptr); 862 void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &); 863 MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool); 864 void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool); 865 void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, 866 SmallPtrSetImpl<BasicBlock *> &Visited, 867 bool SkipVisited = false, bool RenameAllUses = false); 868 AccessList *getOrCreateAccessList(const BasicBlock *); 869 DefsList *getOrCreateDefsList(const BasicBlock *); 870 void renumberBlock(const BasicBlock *) const; 871 AliasAnalysis *AA; 872 DominatorTree *DT; 873 Function &F; 874 875 // Memory SSA mappings 876 DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess; 877 878 // These two mappings contain the main block to access/def mappings for 879 // MemorySSA. The list contained in PerBlockAccesses really owns all the 880 // MemoryAccesses. 881 // Both maps maintain the invariant that if a block is found in them, the 882 // corresponding list is not empty, and if a block is not found in them, the 883 // corresponding list is empty. 884 AccessMap PerBlockAccesses; 885 DefsMap PerBlockDefs; 886 std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef; 887 888 // Domination mappings 889 // Note that the numbering is local to a block, even though the map is 890 // global. 891 mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid; 892 mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering; 893 894 // Memory SSA building info 895 std::unique_ptr<ClobberWalkerBase<AliasAnalysis>> WalkerBase; 896 std::unique_ptr<CachingWalker<AliasAnalysis>> Walker; 897 std::unique_ptr<SkipSelfWalker<AliasAnalysis>> SkipWalker; 898 unsigned NextID; 899 }; 900 901 // Internal MemorySSA utils, for use by MemorySSA classes and walkers 902 class MemorySSAUtil { 903 protected: 904 friend class GVNHoist; 905 friend class MemorySSAWalker; 906 907 // This function should not be used by new passes. 908 static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, 909 AliasAnalysis &AA); 910 }; 911 912 // This pass does eager building and then printing of MemorySSA. It is used by 913 // the tests to be able to build, dump, and verify Memory SSA. 914 class MemorySSAPrinterLegacyPass : public FunctionPass { 915 public: 916 MemorySSAPrinterLegacyPass(); 917 918 bool runOnFunction(Function &) override; 919 void getAnalysisUsage(AnalysisUsage &AU) const override; 920 921 static char ID; 922 }; 923 924 /// An analysis that produces \c MemorySSA for a function. 925 /// 926 class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> { 927 friend AnalysisInfoMixin<MemorySSAAnalysis>; 928 929 static AnalysisKey Key; 930 931 public: 932 // Wrap MemorySSA result to ensure address stability of internal MemorySSA 933 // pointers after construction. Use a wrapper class instead of plain 934 // unique_ptr<MemorySSA> to avoid build breakage on MSVC. 935 struct Result { 936 Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {} 937 938 MemorySSA &getMSSA() { return *MSSA.get(); } 939 940 std::unique_ptr<MemorySSA> MSSA; 941 942 bool invalidate(Function &F, const PreservedAnalyses &PA, 943 FunctionAnalysisManager::Invalidator &Inv); 944 }; 945 946 Result run(Function &F, FunctionAnalysisManager &AM); 947 }; 948 949 /// Printer pass for \c MemorySSA. 950 class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> { 951 raw_ostream &OS; 952 953 public: 954 explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {} 955 956 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 957 }; 958 959 /// Verifier pass for \c MemorySSA. 960 struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> { 961 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 962 }; 963 964 /// Legacy analysis pass which computes \c MemorySSA. 965 class MemorySSAWrapperPass : public FunctionPass { 966 public: 967 MemorySSAWrapperPass(); 968 969 static char ID; 970 971 bool runOnFunction(Function &) override; 972 void releaseMemory() override; 973 MemorySSA &getMSSA() { return *MSSA; } 974 const MemorySSA &getMSSA() const { return *MSSA; } 975 976 void getAnalysisUsage(AnalysisUsage &AU) const override; 977 978 void verifyAnalysis() const override; 979 void print(raw_ostream &OS, const Module *M = nullptr) const override; 980 981 private: 982 std::unique_ptr<MemorySSA> MSSA; 983 }; 984 985 /// This is the generic walker interface for walkers of MemorySSA. 986 /// Walkers are used to be able to further disambiguate the def-use chains 987 /// MemorySSA gives you, or otherwise produce better info than MemorySSA gives 988 /// you. 989 /// In particular, while the def-use chains provide basic information, and are 990 /// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a 991 /// MemoryUse as AliasAnalysis considers it, a user mant want better or other 992 /// information. In particular, they may want to use SCEV info to further 993 /// disambiguate memory accesses, or they may want the nearest dominating 994 /// may-aliasing MemoryDef for a call or a store. This API enables a 995 /// standardized interface to getting and using that info. 996 class MemorySSAWalker { 997 public: 998 MemorySSAWalker(MemorySSA *); 999 virtual ~MemorySSAWalker() = default; 1000 1001 using MemoryAccessSet = SmallVector<MemoryAccess *, 8>; 1002 1003 /// Given a memory Mod/Ref/ModRef'ing instruction, calling this 1004 /// will give you the nearest dominating MemoryAccess that Mod's the location 1005 /// the instruction accesses (by skipping any def which AA can prove does not 1006 /// alias the location(s) accessed by the instruction given). 1007 /// 1008 /// Note that this will return a single access, and it must dominate the 1009 /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction, 1010 /// this will return the MemoryPhi, not the operand. This means that 1011 /// given: 1012 /// if (a) { 1013 /// 1 = MemoryDef(liveOnEntry) 1014 /// store %a 1015 /// } else { 1016 /// 2 = MemoryDef(liveOnEntry) 1017 /// store %b 1018 /// } 1019 /// 3 = MemoryPhi(2, 1) 1020 /// MemoryUse(3) 1021 /// load %a 1022 /// 1023 /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef 1024 /// in the if (a) branch. 1025 MemoryAccess *getClobberingMemoryAccess(const Instruction *I) { 1026 MemoryAccess *MA = MSSA->getMemoryAccess(I); 1027 assert(MA && "Handed an instruction that MemorySSA doesn't recognize?"); 1028 return getClobberingMemoryAccess(MA); 1029 } 1030 1031 /// Does the same thing as getClobberingMemoryAccess(const Instruction *I), 1032 /// but takes a MemoryAccess instead of an Instruction. 1033 virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 0; 1034 1035 /// Given a potentially clobbering memory access and a new location, 1036 /// calling this will give you the nearest dominating clobbering MemoryAccess 1037 /// (by skipping non-aliasing def links). 1038 /// 1039 /// This version of the function is mainly used to disambiguate phi translated 1040 /// pointers, where the value of a pointer may have changed from the initial 1041 /// memory access. Note that this expects to be handed either a MemoryUse, 1042 /// or an already potentially clobbering access. Unlike the above API, if 1043 /// given a MemoryDef that clobbers the pointer as the starting access, it 1044 /// will return that MemoryDef, whereas the above would return the clobber 1045 /// starting from the use side of the memory def. 1046 virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, 1047 const MemoryLocation &) = 0; 1048 1049 /// Given a memory access, invalidate anything this walker knows about 1050 /// that access. 1051 /// This API is used by walkers that store information to perform basic cache 1052 /// invalidation. This will be called by MemorySSA at appropriate times for 1053 /// the walker it uses or returns. 1054 virtual void invalidateInfo(MemoryAccess *) {} 1055 1056 protected: 1057 friend class MemorySSA; // For updating MSSA pointer in MemorySSA move 1058 // constructor. 1059 MemorySSA *MSSA; 1060 }; 1061 1062 /// A MemorySSAWalker that does no alias queries, or anything else. It 1063 /// simply returns the links as they were constructed by the builder. 1064 class DoNothingMemorySSAWalker final : public MemorySSAWalker { 1065 public: 1066 // Keep the overrides below from hiding the Instruction overload of 1067 // getClobberingMemoryAccess. 1068 using MemorySSAWalker::getClobberingMemoryAccess; 1069 1070 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override; 1071 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, 1072 const MemoryLocation &) override; 1073 }; 1074 1075 using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>; 1076 using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>; 1077 1078 /// Iterator base class used to implement const and non-const iterators 1079 /// over the defining accesses of a MemoryAccess. 1080 template <class T> 1081 class memoryaccess_def_iterator_base 1082 : public iterator_facade_base<memoryaccess_def_iterator_base<T>, 1083 std::forward_iterator_tag, T, ptrdiff_t, T *, 1084 T *> { 1085 using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base; 1086 1087 public: 1088 memoryaccess_def_iterator_base(T *Start) : Access(Start) {} 1089 memoryaccess_def_iterator_base() = default; 1090 1091 bool operator==(const memoryaccess_def_iterator_base &Other) const { 1092 return Access == Other.Access && (!Access || ArgNo == Other.ArgNo); 1093 } 1094 1095 // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the 1096 // block from the operand in constant time (In a PHINode, the uselist has 1097 // both, so it's just subtraction). We provide it as part of the 1098 // iterator to avoid callers having to linear walk to get the block. 1099 // If the operation becomes constant time on MemoryPHI's, this bit of 1100 // abstraction breaking should be removed. 1101 BasicBlock *getPhiArgBlock() const { 1102 MemoryPhi *MP = dyn_cast<MemoryPhi>(Access); 1103 assert(MP && "Tried to get phi arg block when not iterating over a PHI"); 1104 return MP->getIncomingBlock(ArgNo); 1105 } 1106 1107 typename std::iterator_traits<BaseT>::pointer operator*() const { 1108 assert(Access && "Tried to access past the end of our iterator"); 1109 // Go to the first argument for phis, and the defining access for everything 1110 // else. 1111 if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) 1112 return MP->getIncomingValue(ArgNo); 1113 return cast<MemoryUseOrDef>(Access)->getDefiningAccess(); 1114 } 1115 1116 using BaseT::operator++; 1117 memoryaccess_def_iterator_base &operator++() { 1118 assert(Access && "Hit end of iterator"); 1119 if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) { 1120 if (++ArgNo >= MP->getNumIncomingValues()) { 1121 ArgNo = 0; 1122 Access = nullptr; 1123 } 1124 } else { 1125 Access = nullptr; 1126 } 1127 return *this; 1128 } 1129 1130 private: 1131 T *Access = nullptr; 1132 unsigned ArgNo = 0; 1133 }; 1134 1135 inline memoryaccess_def_iterator MemoryAccess::defs_begin() { 1136 return memoryaccess_def_iterator(this); 1137 } 1138 1139 inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const { 1140 return const_memoryaccess_def_iterator(this); 1141 } 1142 1143 inline memoryaccess_def_iterator MemoryAccess::defs_end() { 1144 return memoryaccess_def_iterator(); 1145 } 1146 1147 inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const { 1148 return const_memoryaccess_def_iterator(); 1149 } 1150 1151 /// GraphTraits for a MemoryAccess, which walks defs in the normal case, 1152 /// and uses in the inverse case. 1153 template <> struct GraphTraits<MemoryAccess *> { 1154 using NodeRef = MemoryAccess *; 1155 using ChildIteratorType = memoryaccess_def_iterator; 1156 1157 static NodeRef getEntryNode(NodeRef N) { return N; } 1158 static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); } 1159 static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); } 1160 }; 1161 1162 template <> struct GraphTraits<Inverse<MemoryAccess *>> { 1163 using NodeRef = MemoryAccess *; 1164 using ChildIteratorType = MemoryAccess::iterator; 1165 1166 static NodeRef getEntryNode(NodeRef N) { return N; } 1167 static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); } 1168 static ChildIteratorType child_end(NodeRef N) { return N->user_end(); } 1169 }; 1170 1171 /// Provide an iterator that walks defs, giving both the memory access, 1172 /// and the current pointer location, updating the pointer location as it 1173 /// changes due to phi node translation. 1174 /// 1175 /// This iterator, while somewhat specialized, is what most clients actually 1176 /// want when walking upwards through MemorySSA def chains. It takes a pair of 1177 /// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the 1178 /// memory location through phi nodes for the user. 1179 class upward_defs_iterator 1180 : public iterator_facade_base<upward_defs_iterator, 1181 std::forward_iterator_tag, 1182 const MemoryAccessPair> { 1183 using BaseT = upward_defs_iterator::iterator_facade_base; 1184 1185 public: 1186 upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT, 1187 bool *PerformedPhiTranslation = nullptr) 1188 : DefIterator(Info.first), Location(Info.second), 1189 OriginalAccess(Info.first), DT(DT), 1190 PerformedPhiTranslation(PerformedPhiTranslation) { 1191 CurrentPair.first = nullptr; 1192 1193 WalkingPhi = Info.first && isa<MemoryPhi>(Info.first); 1194 fillInCurrentPair(); 1195 } 1196 1197 upward_defs_iterator() { CurrentPair.first = nullptr; } 1198 1199 bool operator==(const upward_defs_iterator &Other) const { 1200 return DefIterator == Other.DefIterator; 1201 } 1202 1203 typename std::iterator_traits<BaseT>::reference operator*() const { 1204 assert(DefIterator != OriginalAccess->defs_end() && 1205 "Tried to access past the end of our iterator"); 1206 return CurrentPair; 1207 } 1208 1209 using BaseT::operator++; 1210 upward_defs_iterator &operator++() { 1211 assert(DefIterator != OriginalAccess->defs_end() && 1212 "Tried to access past the end of the iterator"); 1213 ++DefIterator; 1214 if (DefIterator != OriginalAccess->defs_end()) 1215 fillInCurrentPair(); 1216 return *this; 1217 } 1218 1219 BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); } 1220 1221 private: 1222 /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible 1223 /// loop. In particular, this guarantees that it only references a single 1224 /// MemoryLocation during execution of the containing function. 1225 bool IsGuaranteedLoopInvariant(Value *Ptr) const; 1226 1227 void fillInCurrentPair() { 1228 CurrentPair.first = *DefIterator; 1229 CurrentPair.second = Location; 1230 if (WalkingPhi && Location.Ptr) { 1231 // Mark size as unknown, if the location is not guaranteed to be 1232 // loop-invariant for any possible loop in the function. Setting the size 1233 // to unknown guarantees that any memory accesses that access locations 1234 // after the pointer are considered as clobbers, which is important to 1235 // catch loop carried dependences. 1236 if (Location.Ptr && 1237 !IsGuaranteedLoopInvariant(const_cast<Value *>(Location.Ptr))) 1238 CurrentPair.second = 1239 Location.getWithNewSize(LocationSize::beforeOrAfterPointer()); 1240 PHITransAddr Translator( 1241 const_cast<Value *>(Location.Ptr), 1242 OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr); 1243 1244 if (!Translator.PHITranslateValue(OriginalAccess->getBlock(), 1245 DefIterator.getPhiArgBlock(), DT, 1246 true)) { 1247 Value *TransAddr = Translator.getAddr(); 1248 if (TransAddr != Location.Ptr) { 1249 CurrentPair.second = CurrentPair.second.getWithNewPtr(TransAddr); 1250 1251 if (TransAddr && 1252 !IsGuaranteedLoopInvariant(const_cast<Value *>(TransAddr))) 1253 CurrentPair.second = CurrentPair.second.getWithNewSize( 1254 LocationSize::beforeOrAfterPointer()); 1255 1256 if (PerformedPhiTranslation) 1257 *PerformedPhiTranslation = true; 1258 } 1259 } 1260 } 1261 } 1262 1263 MemoryAccessPair CurrentPair; 1264 memoryaccess_def_iterator DefIterator; 1265 MemoryLocation Location; 1266 MemoryAccess *OriginalAccess = nullptr; 1267 DominatorTree *DT = nullptr; 1268 bool WalkingPhi = false; 1269 bool *PerformedPhiTranslation = nullptr; 1270 }; 1271 1272 inline upward_defs_iterator 1273 upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT, 1274 bool *PerformedPhiTranslation = nullptr) { 1275 return upward_defs_iterator(Pair, &DT, PerformedPhiTranslation); 1276 } 1277 1278 inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); } 1279 1280 inline iterator_range<upward_defs_iterator> 1281 upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT) { 1282 return make_range(upward_defs_begin(Pair, DT), upward_defs_end()); 1283 } 1284 1285 /// Walks the defining accesses of MemoryDefs. Stops after we hit something that 1286 /// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when 1287 /// comparing against a null def_chain_iterator, this will compare equal only 1288 /// after walking said Phi/liveOnEntry. 1289 /// 1290 /// The UseOptimizedChain flag specifies whether to walk the clobbering 1291 /// access chain, or all the accesses. 1292 /// 1293 /// Normally, MemoryDef are all just def/use linked together, so a def_chain on 1294 /// a MemoryDef will walk all MemoryDefs above it in the program until it hits 1295 /// a phi node. The optimized chain walks the clobbering access of a store. 1296 /// So if you are just trying to find, given a store, what the next 1297 /// thing that would clobber the same memory is, you want the optimized chain. 1298 template <class T, bool UseOptimizedChain = false> 1299 struct def_chain_iterator 1300 : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>, 1301 std::forward_iterator_tag, MemoryAccess *> { 1302 def_chain_iterator() : MA(nullptr) {} 1303 def_chain_iterator(T MA) : MA(MA) {} 1304 1305 T operator*() const { return MA; } 1306 1307 def_chain_iterator &operator++() { 1308 // N.B. liveOnEntry has a null defining access. 1309 if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) { 1310 if (UseOptimizedChain && MUD->isOptimized()) 1311 MA = MUD->getOptimized(); 1312 else 1313 MA = MUD->getDefiningAccess(); 1314 } else { 1315 MA = nullptr; 1316 } 1317 1318 return *this; 1319 } 1320 1321 bool operator==(const def_chain_iterator &O) const { return MA == O.MA; } 1322 1323 private: 1324 T MA; 1325 }; 1326 1327 template <class T> 1328 inline iterator_range<def_chain_iterator<T>> 1329 def_chain(T MA, MemoryAccess *UpTo = nullptr) { 1330 #ifdef EXPENSIVE_CHECKS 1331 assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) && 1332 "UpTo isn't in the def chain!"); 1333 #endif 1334 return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo)); 1335 } 1336 1337 template <class T> 1338 inline iterator_range<def_chain_iterator<T, true>> optimized_def_chain(T MA) { 1339 return make_range(def_chain_iterator<T, true>(MA), 1340 def_chain_iterator<T, true>(nullptr)); 1341 } 1342 1343 } // end namespace llvm 1344 1345 #endif // LLVM_ANALYSIS_MEMORYSSA_H 1346