1 //===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===// 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 // Rewrite call/invoke instructions so as to make potential relocations 10 // performed by the garbage collector explicit in the IR. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Scalar/RewriteStatepointsForGC.h" 15 16 #include "llvm/ADT/ArrayRef.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/DenseSet.h" 19 #include "llvm/ADT/MapVector.h" 20 #include "llvm/ADT/None.h" 21 #include "llvm/ADT/Optional.h" 22 #include "llvm/ADT/STLExtras.h" 23 #include "llvm/ADT/SetVector.h" 24 #include "llvm/ADT/SmallSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/StringRef.h" 27 #include "llvm/ADT/iterator_range.h" 28 #include "llvm/Analysis/DomTreeUpdater.h" 29 #include "llvm/Analysis/TargetLibraryInfo.h" 30 #include "llvm/Analysis/TargetTransformInfo.h" 31 #include "llvm/IR/Argument.h" 32 #include "llvm/IR/Attributes.h" 33 #include "llvm/IR/BasicBlock.h" 34 #include "llvm/IR/CallingConv.h" 35 #include "llvm/IR/Constant.h" 36 #include "llvm/IR/Constants.h" 37 #include "llvm/IR/DataLayout.h" 38 #include "llvm/IR/DerivedTypes.h" 39 #include "llvm/IR/Dominators.h" 40 #include "llvm/IR/Function.h" 41 #include "llvm/IR/IRBuilder.h" 42 #include "llvm/IR/InstIterator.h" 43 #include "llvm/IR/InstrTypes.h" 44 #include "llvm/IR/Instruction.h" 45 #include "llvm/IR/Instructions.h" 46 #include "llvm/IR/IntrinsicInst.h" 47 #include "llvm/IR/Intrinsics.h" 48 #include "llvm/IR/LLVMContext.h" 49 #include "llvm/IR/MDBuilder.h" 50 #include "llvm/IR/Metadata.h" 51 #include "llvm/IR/Module.h" 52 #include "llvm/IR/Statepoint.h" 53 #include "llvm/IR/Type.h" 54 #include "llvm/IR/User.h" 55 #include "llvm/IR/Value.h" 56 #include "llvm/IR/ValueHandle.h" 57 #include "llvm/InitializePasses.h" 58 #include "llvm/Pass.h" 59 #include "llvm/Support/Casting.h" 60 #include "llvm/Support/CommandLine.h" 61 #include "llvm/Support/Compiler.h" 62 #include "llvm/Support/Debug.h" 63 #include "llvm/Support/ErrorHandling.h" 64 #include "llvm/Support/raw_ostream.h" 65 #include "llvm/Transforms/Scalar.h" 66 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 67 #include "llvm/Transforms/Utils/Local.h" 68 #include "llvm/Transforms/Utils/PromoteMemToReg.h" 69 #include <algorithm> 70 #include <cassert> 71 #include <cstddef> 72 #include <cstdint> 73 #include <iterator> 74 #include <set> 75 #include <string> 76 #include <utility> 77 #include <vector> 78 79 #define DEBUG_TYPE "rewrite-statepoints-for-gc" 80 81 using namespace llvm; 82 83 // Print the liveset found at the insert location 84 static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden, 85 cl::init(false)); 86 static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden, 87 cl::init(false)); 88 89 // Print out the base pointers for debugging 90 static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden, 91 cl::init(false)); 92 93 // Cost threshold measuring when it is profitable to rematerialize value instead 94 // of relocating it 95 static cl::opt<unsigned> 96 RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden, 97 cl::init(6)); 98 99 #ifdef EXPENSIVE_CHECKS 100 static bool ClobberNonLive = true; 101 #else 102 static bool ClobberNonLive = false; 103 #endif 104 105 static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live", 106 cl::location(ClobberNonLive), 107 cl::Hidden); 108 109 static cl::opt<bool> 110 AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", 111 cl::Hidden, cl::init(true)); 112 113 /// The IR fed into RewriteStatepointsForGC may have had attributes and 114 /// metadata implying dereferenceability that are no longer valid/correct after 115 /// RewriteStatepointsForGC has run. This is because semantically, after 116 /// RewriteStatepointsForGC runs, all calls to gc.statepoint "free" the entire 117 /// heap. stripNonValidData (conservatively) restores 118 /// correctness by erasing all attributes in the module that externally imply 119 /// dereferenceability. Similar reasoning also applies to the noalias 120 /// attributes and metadata. gc.statepoint can touch the entire heap including 121 /// noalias objects. 122 /// Apart from attributes and metadata, we also remove instructions that imply 123 /// constant physical memory: llvm.invariant.start. 124 static void stripNonValidData(Module &M); 125 126 static bool shouldRewriteStatepointsIn(Function &F); 127 128 PreservedAnalyses RewriteStatepointsForGC::run(Module &M, 129 ModuleAnalysisManager &AM) { 130 bool Changed = false; 131 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 132 for (Function &F : M) { 133 // Nothing to do for declarations. 134 if (F.isDeclaration() || F.empty()) 135 continue; 136 137 // Policy choice says not to rewrite - the most common reason is that we're 138 // compiling code without a GCStrategy. 139 if (!shouldRewriteStatepointsIn(F)) 140 continue; 141 142 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F); 143 auto &TTI = FAM.getResult<TargetIRAnalysis>(F); 144 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F); 145 Changed |= runOnFunction(F, DT, TTI, TLI); 146 } 147 if (!Changed) 148 return PreservedAnalyses::all(); 149 150 // stripNonValidData asserts that shouldRewriteStatepointsIn 151 // returns true for at least one function in the module. Since at least 152 // one function changed, we know that the precondition is satisfied. 153 stripNonValidData(M); 154 155 PreservedAnalyses PA; 156 PA.preserve<TargetIRAnalysis>(); 157 PA.preserve<TargetLibraryAnalysis>(); 158 return PA; 159 } 160 161 namespace { 162 163 class RewriteStatepointsForGCLegacyPass : public ModulePass { 164 RewriteStatepointsForGC Impl; 165 166 public: 167 static char ID; // Pass identification, replacement for typeid 168 169 RewriteStatepointsForGCLegacyPass() : ModulePass(ID), Impl() { 170 initializeRewriteStatepointsForGCLegacyPassPass( 171 *PassRegistry::getPassRegistry()); 172 } 173 174 bool runOnModule(Module &M) override { 175 bool Changed = false; 176 for (Function &F : M) { 177 // Nothing to do for declarations. 178 if (F.isDeclaration() || F.empty()) 179 continue; 180 181 // Policy choice says not to rewrite - the most common reason is that 182 // we're compiling code without a GCStrategy. 183 if (!shouldRewriteStatepointsIn(F)) 184 continue; 185 186 TargetTransformInfo &TTI = 187 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 188 const TargetLibraryInfo &TLI = 189 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 190 auto &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(); 191 192 Changed |= Impl.runOnFunction(F, DT, TTI, TLI); 193 } 194 195 if (!Changed) 196 return false; 197 198 // stripNonValidData asserts that shouldRewriteStatepointsIn 199 // returns true for at least one function in the module. Since at least 200 // one function changed, we know that the precondition is satisfied. 201 stripNonValidData(M); 202 return true; 203 } 204 205 void getAnalysisUsage(AnalysisUsage &AU) const override { 206 // We add and rewrite a bunch of instructions, but don't really do much 207 // else. We could in theory preserve a lot more analyses here. 208 AU.addRequired<DominatorTreeWrapperPass>(); 209 AU.addRequired<TargetTransformInfoWrapperPass>(); 210 AU.addRequired<TargetLibraryInfoWrapperPass>(); 211 } 212 }; 213 214 } // end anonymous namespace 215 216 char RewriteStatepointsForGCLegacyPass::ID = 0; 217 218 ModulePass *llvm::createRewriteStatepointsForGCLegacyPass() { 219 return new RewriteStatepointsForGCLegacyPass(); 220 } 221 222 INITIALIZE_PASS_BEGIN(RewriteStatepointsForGCLegacyPass, 223 "rewrite-statepoints-for-gc", 224 "Make relocations explicit at statepoints", false, false) 225 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 226 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 227 INITIALIZE_PASS_END(RewriteStatepointsForGCLegacyPass, 228 "rewrite-statepoints-for-gc", 229 "Make relocations explicit at statepoints", false, false) 230 231 namespace { 232 233 struct GCPtrLivenessData { 234 /// Values defined in this block. 235 MapVector<BasicBlock *, SetVector<Value *>> KillSet; 236 237 /// Values used in this block (and thus live); does not included values 238 /// killed within this block. 239 MapVector<BasicBlock *, SetVector<Value *>> LiveSet; 240 241 /// Values live into this basic block (i.e. used by any 242 /// instruction in this basic block or ones reachable from here) 243 MapVector<BasicBlock *, SetVector<Value *>> LiveIn; 244 245 /// Values live out of this basic block (i.e. live into 246 /// any successor block) 247 MapVector<BasicBlock *, SetVector<Value *>> LiveOut; 248 }; 249 250 // The type of the internal cache used inside the findBasePointers family 251 // of functions. From the callers perspective, this is an opaque type and 252 // should not be inspected. 253 // 254 // In the actual implementation this caches two relations: 255 // - The base relation itself (i.e. this pointer is based on that one) 256 // - The base defining value relation (i.e. before base_phi insertion) 257 // Generally, after the execution of a full findBasePointer call, only the 258 // base relation will remain. Internally, we add a mixture of the two 259 // types, then update all the second type to the first type 260 using DefiningValueMapTy = MapVector<Value *, Value *>; 261 using StatepointLiveSetTy = SetVector<Value *>; 262 using RematerializedValueMapTy = 263 MapVector<AssertingVH<Instruction>, AssertingVH<Value>>; 264 265 struct PartiallyConstructedSafepointRecord { 266 /// The set of values known to be live across this safepoint 267 StatepointLiveSetTy LiveSet; 268 269 /// Mapping from live pointers to a base-defining-value 270 MapVector<Value *, Value *> PointerToBase; 271 272 /// The *new* gc.statepoint instruction itself. This produces the token 273 /// that normal path gc.relocates and the gc.result are tied to. 274 Instruction *StatepointToken; 275 276 /// Instruction to which exceptional gc relocates are attached 277 /// Makes it easier to iterate through them during relocationViaAlloca. 278 Instruction *UnwindToken; 279 280 /// Record live values we are rematerialized instead of relocating. 281 /// They are not included into 'LiveSet' field. 282 /// Maps rematerialized copy to it's original value. 283 RematerializedValueMapTy RematerializedValues; 284 }; 285 286 } // end anonymous namespace 287 288 static ArrayRef<Use> GetDeoptBundleOperands(const CallBase *Call) { 289 Optional<OperandBundleUse> DeoptBundle = 290 Call->getOperandBundle(LLVMContext::OB_deopt); 291 292 if (!DeoptBundle.hasValue()) { 293 assert(AllowStatepointWithNoDeoptInfo && 294 "Found non-leaf call without deopt info!"); 295 return None; 296 } 297 298 return DeoptBundle.getValue().Inputs; 299 } 300 301 /// Compute the live-in set for every basic block in the function 302 static void computeLiveInValues(DominatorTree &DT, Function &F, 303 GCPtrLivenessData &Data); 304 305 /// Given results from the dataflow liveness computation, find the set of live 306 /// Values at a particular instruction. 307 static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data, 308 StatepointLiveSetTy &out); 309 310 // TODO: Once we can get to the GCStrategy, this becomes 311 // Optional<bool> isGCManagedPointer(const Type *Ty) const override { 312 313 static bool isGCPointerType(Type *T) { 314 if (auto *PT = dyn_cast<PointerType>(T)) 315 // For the sake of this example GC, we arbitrarily pick addrspace(1) as our 316 // GC managed heap. We know that a pointer into this heap needs to be 317 // updated and that no other pointer does. 318 return PT->getAddressSpace() == 1; 319 return false; 320 } 321 322 // Return true if this type is one which a) is a gc pointer or contains a GC 323 // pointer and b) is of a type this code expects to encounter as a live value. 324 // (The insertion code will assert that a type which matches (a) and not (b) 325 // is not encountered.) 326 static bool isHandledGCPointerType(Type *T) { 327 // We fully support gc pointers 328 if (isGCPointerType(T)) 329 return true; 330 // We partially support vectors of gc pointers. The code will assert if it 331 // can't handle something. 332 if (auto VT = dyn_cast<VectorType>(T)) 333 if (isGCPointerType(VT->getElementType())) 334 return true; 335 return false; 336 } 337 338 #ifndef NDEBUG 339 /// Returns true if this type contains a gc pointer whether we know how to 340 /// handle that type or not. 341 static bool containsGCPtrType(Type *Ty) { 342 if (isGCPointerType(Ty)) 343 return true; 344 if (VectorType *VT = dyn_cast<VectorType>(Ty)) 345 return isGCPointerType(VT->getScalarType()); 346 if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) 347 return containsGCPtrType(AT->getElementType()); 348 if (StructType *ST = dyn_cast<StructType>(Ty)) 349 return llvm::any_of(ST->elements(), containsGCPtrType); 350 return false; 351 } 352 353 // Returns true if this is a type which a) is a gc pointer or contains a GC 354 // pointer and b) is of a type which the code doesn't expect (i.e. first class 355 // aggregates). Used to trip assertions. 356 static bool isUnhandledGCPointerType(Type *Ty) { 357 return containsGCPtrType(Ty) && !isHandledGCPointerType(Ty); 358 } 359 #endif 360 361 // Return the name of the value suffixed with the provided value, or if the 362 // value didn't have a name, the default value specified. 363 static std::string suffixed_name_or(Value *V, StringRef Suffix, 364 StringRef DefaultName) { 365 return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str(); 366 } 367 368 // Conservatively identifies any definitions which might be live at the 369 // given instruction. The analysis is performed immediately before the 370 // given instruction. Values defined by that instruction are not considered 371 // live. Values used by that instruction are considered live. 372 static void analyzeParsePointLiveness( 373 DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call, 374 PartiallyConstructedSafepointRecord &Result) { 375 StatepointLiveSetTy LiveSet; 376 findLiveSetAtInst(Call, OriginalLivenessData, LiveSet); 377 378 if (PrintLiveSet) { 379 dbgs() << "Live Variables:\n"; 380 for (Value *V : LiveSet) 381 dbgs() << " " << V->getName() << " " << *V << "\n"; 382 } 383 if (PrintLiveSetSize) { 384 dbgs() << "Safepoint For: " << Call->getCalledValue()->getName() << "\n"; 385 dbgs() << "Number live values: " << LiveSet.size() << "\n"; 386 } 387 Result.LiveSet = LiveSet; 388 } 389 390 static bool isKnownBaseResult(Value *V); 391 392 namespace { 393 394 /// A single base defining value - An immediate base defining value for an 395 /// instruction 'Def' is an input to 'Def' whose base is also a base of 'Def'. 396 /// For instructions which have multiple pointer [vector] inputs or that 397 /// transition between vector and scalar types, there is no immediate base 398 /// defining value. The 'base defining value' for 'Def' is the transitive 399 /// closure of this relation stopping at the first instruction which has no 400 /// immediate base defining value. The b.d.v. might itself be a base pointer, 401 /// but it can also be an arbitrary derived pointer. 402 struct BaseDefiningValueResult { 403 /// Contains the value which is the base defining value. 404 Value * const BDV; 405 406 /// True if the base defining value is also known to be an actual base 407 /// pointer. 408 const bool IsKnownBase; 409 410 BaseDefiningValueResult(Value *BDV, bool IsKnownBase) 411 : BDV(BDV), IsKnownBase(IsKnownBase) { 412 #ifndef NDEBUG 413 // Check consistency between new and old means of checking whether a BDV is 414 // a base. 415 bool MustBeBase = isKnownBaseResult(BDV); 416 assert(!MustBeBase || MustBeBase == IsKnownBase); 417 #endif 418 } 419 }; 420 421 } // end anonymous namespace 422 423 static BaseDefiningValueResult findBaseDefiningValue(Value *I); 424 425 /// Return a base defining value for the 'Index' element of the given vector 426 /// instruction 'I'. If Index is null, returns a BDV for the entire vector 427 /// 'I'. As an optimization, this method will try to determine when the 428 /// element is known to already be a base pointer. If this can be established, 429 /// the second value in the returned pair will be true. Note that either a 430 /// vector or a pointer typed value can be returned. For the former, the 431 /// vector returned is a BDV (and possibly a base) of the entire vector 'I'. 432 /// If the later, the return pointer is a BDV (or possibly a base) for the 433 /// particular element in 'I'. 434 static BaseDefiningValueResult 435 findBaseDefiningValueOfVector(Value *I) { 436 // Each case parallels findBaseDefiningValue below, see that code for 437 // detailed motivation. 438 439 if (isa<Argument>(I)) 440 // An incoming argument to the function is a base pointer 441 return BaseDefiningValueResult(I, true); 442 443 if (isa<Constant>(I)) 444 // Base of constant vector consists only of constant null pointers. 445 // For reasoning see similar case inside 'findBaseDefiningValue' function. 446 return BaseDefiningValueResult(ConstantAggregateZero::get(I->getType()), 447 true); 448 449 if (isa<LoadInst>(I)) 450 return BaseDefiningValueResult(I, true); 451 452 if (isa<InsertElementInst>(I)) 453 // We don't know whether this vector contains entirely base pointers or 454 // not. To be conservatively correct, we treat it as a BDV and will 455 // duplicate code as needed to construct a parallel vector of bases. 456 return BaseDefiningValueResult(I, false); 457 458 if (isa<ShuffleVectorInst>(I)) 459 // We don't know whether this vector contains entirely base pointers or 460 // not. To be conservatively correct, we treat it as a BDV and will 461 // duplicate code as needed to construct a parallel vector of bases. 462 // TODO: There a number of local optimizations which could be applied here 463 // for particular sufflevector patterns. 464 return BaseDefiningValueResult(I, false); 465 466 // The behavior of getelementptr instructions is the same for vector and 467 // non-vector data types. 468 if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) 469 return findBaseDefiningValue(GEP->getPointerOperand()); 470 471 // If the pointer comes through a bitcast of a vector of pointers to 472 // a vector of another type of pointer, then look through the bitcast 473 if (auto *BC = dyn_cast<BitCastInst>(I)) 474 return findBaseDefiningValue(BC->getOperand(0)); 475 476 // We assume that functions in the source language only return base 477 // pointers. This should probably be generalized via attributes to support 478 // both source language and internal functions. 479 if (isa<CallInst>(I) || isa<InvokeInst>(I)) 480 return BaseDefiningValueResult(I, true); 481 482 // A PHI or Select is a base defining value. The outer findBasePointer 483 // algorithm is responsible for constructing a base value for this BDV. 484 assert((isa<SelectInst>(I) || isa<PHINode>(I)) && 485 "unknown vector instruction - no base found for vector element"); 486 return BaseDefiningValueResult(I, false); 487 } 488 489 /// Helper function for findBasePointer - Will return a value which either a) 490 /// defines the base pointer for the input, b) blocks the simple search 491 /// (i.e. a PHI or Select of two derived pointers), or c) involves a change 492 /// from pointer to vector type or back. 493 static BaseDefiningValueResult findBaseDefiningValue(Value *I) { 494 assert(I->getType()->isPtrOrPtrVectorTy() && 495 "Illegal to ask for the base pointer of a non-pointer type"); 496 497 if (I->getType()->isVectorTy()) 498 return findBaseDefiningValueOfVector(I); 499 500 if (isa<Argument>(I)) 501 // An incoming argument to the function is a base pointer 502 // We should have never reached here if this argument isn't an gc value 503 return BaseDefiningValueResult(I, true); 504 505 if (isa<Constant>(I)) { 506 // We assume that objects with a constant base (e.g. a global) can't move 507 // and don't need to be reported to the collector because they are always 508 // live. Besides global references, all kinds of constants (e.g. undef, 509 // constant expressions, null pointers) can be introduced by the inliner or 510 // the optimizer, especially on dynamically dead paths. 511 // Here we treat all of them as having single null base. By doing this we 512 // trying to avoid problems reporting various conflicts in a form of 513 // "phi (const1, const2)" or "phi (const, regular gc ptr)". 514 // See constant.ll file for relevant test cases. 515 516 return BaseDefiningValueResult( 517 ConstantPointerNull::get(cast<PointerType>(I->getType())), true); 518 } 519 520 if (CastInst *CI = dyn_cast<CastInst>(I)) { 521 Value *Def = CI->stripPointerCasts(); 522 // If stripping pointer casts changes the address space there is an 523 // addrspacecast in between. 524 assert(cast<PointerType>(Def->getType())->getAddressSpace() == 525 cast<PointerType>(CI->getType())->getAddressSpace() && 526 "unsupported addrspacecast"); 527 // If we find a cast instruction here, it means we've found a cast which is 528 // not simply a pointer cast (i.e. an inttoptr). We don't know how to 529 // handle int->ptr conversion. 530 assert(!isa<CastInst>(Def) && "shouldn't find another cast here"); 531 return findBaseDefiningValue(Def); 532 } 533 534 if (isa<LoadInst>(I)) 535 // The value loaded is an gc base itself 536 return BaseDefiningValueResult(I, true); 537 538 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) 539 // The base of this GEP is the base 540 return findBaseDefiningValue(GEP->getPointerOperand()); 541 542 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 543 switch (II->getIntrinsicID()) { 544 default: 545 // fall through to general call handling 546 break; 547 case Intrinsic::experimental_gc_statepoint: 548 llvm_unreachable("statepoints don't produce pointers"); 549 case Intrinsic::experimental_gc_relocate: 550 // Rerunning safepoint insertion after safepoints are already 551 // inserted is not supported. It could probably be made to work, 552 // but why are you doing this? There's no good reason. 553 llvm_unreachable("repeat safepoint insertion is not supported"); 554 case Intrinsic::gcroot: 555 // Currently, this mechanism hasn't been extended to work with gcroot. 556 // There's no reason it couldn't be, but I haven't thought about the 557 // implications much. 558 llvm_unreachable( 559 "interaction with the gcroot mechanism is not supported"); 560 } 561 } 562 // We assume that functions in the source language only return base 563 // pointers. This should probably be generalized via attributes to support 564 // both source language and internal functions. 565 if (isa<CallInst>(I) || isa<InvokeInst>(I)) 566 return BaseDefiningValueResult(I, true); 567 568 // TODO: I have absolutely no idea how to implement this part yet. It's not 569 // necessarily hard, I just haven't really looked at it yet. 570 assert(!isa<LandingPadInst>(I) && "Landing Pad is unimplemented"); 571 572 if (isa<AtomicCmpXchgInst>(I)) 573 // A CAS is effectively a atomic store and load combined under a 574 // predicate. From the perspective of base pointers, we just treat it 575 // like a load. 576 return BaseDefiningValueResult(I, true); 577 578 assert(!isa<AtomicRMWInst>(I) && "Xchg handled above, all others are " 579 "binary ops which don't apply to pointers"); 580 581 // The aggregate ops. Aggregates can either be in the heap or on the 582 // stack, but in either case, this is simply a field load. As a result, 583 // this is a defining definition of the base just like a load is. 584 if (isa<ExtractValueInst>(I)) 585 return BaseDefiningValueResult(I, true); 586 587 // We should never see an insert vector since that would require we be 588 // tracing back a struct value not a pointer value. 589 assert(!isa<InsertValueInst>(I) && 590 "Base pointer for a struct is meaningless"); 591 592 // An extractelement produces a base result exactly when it's input does. 593 // We may need to insert a parallel instruction to extract the appropriate 594 // element out of the base vector corresponding to the input. Given this, 595 // it's analogous to the phi and select case even though it's not a merge. 596 if (isa<ExtractElementInst>(I)) 597 // Note: There a lot of obvious peephole cases here. This are deliberately 598 // handled after the main base pointer inference algorithm to make writing 599 // test cases to exercise that code easier. 600 return BaseDefiningValueResult(I, false); 601 602 // The last two cases here don't return a base pointer. Instead, they 603 // return a value which dynamically selects from among several base 604 // derived pointers (each with it's own base potentially). It's the job of 605 // the caller to resolve these. 606 assert((isa<SelectInst>(I) || isa<PHINode>(I)) && 607 "missing instruction case in findBaseDefiningValing"); 608 return BaseDefiningValueResult(I, false); 609 } 610 611 /// Returns the base defining value for this value. 612 static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache) { 613 Value *&Cached = Cache[I]; 614 if (!Cached) { 615 Cached = findBaseDefiningValue(I).BDV; 616 LLVM_DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> " 617 << Cached->getName() << "\n"); 618 } 619 assert(Cache[I] != nullptr); 620 return Cached; 621 } 622 623 /// Return a base pointer for this value if known. Otherwise, return it's 624 /// base defining value. 625 static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache) { 626 Value *Def = findBaseDefiningValueCached(I, Cache); 627 auto Found = Cache.find(Def); 628 if (Found != Cache.end()) { 629 // Either a base-of relation, or a self reference. Caller must check. 630 return Found->second; 631 } 632 // Only a BDV available 633 return Def; 634 } 635 636 /// Given the result of a call to findBaseDefiningValue, or findBaseOrBDV, 637 /// is it known to be a base pointer? Or do we need to continue searching. 638 static bool isKnownBaseResult(Value *V) { 639 if (!isa<PHINode>(V) && !isa<SelectInst>(V) && 640 !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) && 641 !isa<ShuffleVectorInst>(V)) { 642 // no recursion possible 643 return true; 644 } 645 if (isa<Instruction>(V) && 646 cast<Instruction>(V)->getMetadata("is_base_value")) { 647 // This is a previously inserted base phi or select. We know 648 // that this is a base value. 649 return true; 650 } 651 652 // We need to keep searching 653 return false; 654 } 655 656 namespace { 657 658 /// Models the state of a single base defining value in the findBasePointer 659 /// algorithm for determining where a new instruction is needed to propagate 660 /// the base of this BDV. 661 class BDVState { 662 public: 663 enum Status { Unknown, Base, Conflict }; 664 665 BDVState() : BaseValue(nullptr) {} 666 667 explicit BDVState(Status Status, Value *BaseValue = nullptr) 668 : Status(Status), BaseValue(BaseValue) { 669 assert(Status != Base || BaseValue); 670 } 671 672 explicit BDVState(Value *BaseValue) : Status(Base), BaseValue(BaseValue) {} 673 674 Status getStatus() const { return Status; } 675 Value *getBaseValue() const { return BaseValue; } 676 677 bool isBase() const { return getStatus() == Base; } 678 bool isUnknown() const { return getStatus() == Unknown; } 679 bool isConflict() const { return getStatus() == Conflict; } 680 681 bool operator==(const BDVState &Other) const { 682 return BaseValue == Other.BaseValue && Status == Other.Status; 683 } 684 685 bool operator!=(const BDVState &other) const { return !(*this == other); } 686 687 LLVM_DUMP_METHOD 688 void dump() const { 689 print(dbgs()); 690 dbgs() << '\n'; 691 } 692 693 void print(raw_ostream &OS) const { 694 switch (getStatus()) { 695 case Unknown: 696 OS << "U"; 697 break; 698 case Base: 699 OS << "B"; 700 break; 701 case Conflict: 702 OS << "C"; 703 break; 704 } 705 OS << " (" << getBaseValue() << " - " 706 << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << "): "; 707 } 708 709 private: 710 Status Status = Unknown; 711 AssertingVH<Value> BaseValue; // Non-null only if Status == Base. 712 }; 713 714 } // end anonymous namespace 715 716 #ifndef NDEBUG 717 static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) { 718 State.print(OS); 719 return OS; 720 } 721 #endif 722 723 static BDVState meetBDVStateImpl(const BDVState &LHS, const BDVState &RHS) { 724 switch (LHS.getStatus()) { 725 case BDVState::Unknown: 726 return RHS; 727 728 case BDVState::Base: 729 assert(LHS.getBaseValue() && "can't be null"); 730 if (RHS.isUnknown()) 731 return LHS; 732 733 if (RHS.isBase()) { 734 if (LHS.getBaseValue() == RHS.getBaseValue()) { 735 assert(LHS == RHS && "equality broken!"); 736 return LHS; 737 } 738 return BDVState(BDVState::Conflict); 739 } 740 assert(RHS.isConflict() && "only three states!"); 741 return BDVState(BDVState::Conflict); 742 743 case BDVState::Conflict: 744 return LHS; 745 } 746 llvm_unreachable("only three states!"); 747 } 748 749 // Values of type BDVState form a lattice, and this function implements the meet 750 // operation. 751 static BDVState meetBDVState(const BDVState &LHS, const BDVState &RHS) { 752 BDVState Result = meetBDVStateImpl(LHS, RHS); 753 assert(Result == meetBDVStateImpl(RHS, LHS) && 754 "Math is wrong: meet does not commute!"); 755 return Result; 756 } 757 758 /// For a given value or instruction, figure out what base ptr its derived from. 759 /// For gc objects, this is simply itself. On success, returns a value which is 760 /// the base pointer. (This is reliable and can be used for relocation.) On 761 /// failure, returns nullptr. 762 static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache) { 763 Value *Def = findBaseOrBDV(I, Cache); 764 765 if (isKnownBaseResult(Def)) 766 return Def; 767 768 // Here's the rough algorithm: 769 // - For every SSA value, construct a mapping to either an actual base 770 // pointer or a PHI which obscures the base pointer. 771 // - Construct a mapping from PHI to unknown TOP state. Use an 772 // optimistic algorithm to propagate base pointer information. Lattice 773 // looks like: 774 // UNKNOWN 775 // b1 b2 b3 b4 776 // CONFLICT 777 // When algorithm terminates, all PHIs will either have a single concrete 778 // base or be in a conflict state. 779 // - For every conflict, insert a dummy PHI node without arguments. Add 780 // these to the base[Instruction] = BasePtr mapping. For every 781 // non-conflict, add the actual base. 782 // - For every conflict, add arguments for the base[a] of each input 783 // arguments. 784 // 785 // Note: A simpler form of this would be to add the conflict form of all 786 // PHIs without running the optimistic algorithm. This would be 787 // analogous to pessimistic data flow and would likely lead to an 788 // overall worse solution. 789 790 #ifndef NDEBUG 791 auto isExpectedBDVType = [](Value *BDV) { 792 return isa<PHINode>(BDV) || isa<SelectInst>(BDV) || 793 isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) || 794 isa<ShuffleVectorInst>(BDV); 795 }; 796 #endif 797 798 // Once populated, will contain a mapping from each potentially non-base BDV 799 // to a lattice value (described above) which corresponds to that BDV. 800 // We use the order of insertion (DFS over the def/use graph) to provide a 801 // stable deterministic ordering for visiting DenseMaps (which are unordered) 802 // below. This is important for deterministic compilation. 803 MapVector<Value *, BDVState> States; 804 805 // Recursively fill in all base defining values reachable from the initial 806 // one for which we don't already know a definite base value for 807 /* scope */ { 808 SmallVector<Value*, 16> Worklist; 809 Worklist.push_back(Def); 810 States.insert({Def, BDVState()}); 811 while (!Worklist.empty()) { 812 Value *Current = Worklist.pop_back_val(); 813 assert(!isKnownBaseResult(Current) && "why did it get added?"); 814 815 auto visitIncomingValue = [&](Value *InVal) { 816 Value *Base = findBaseOrBDV(InVal, Cache); 817 if (isKnownBaseResult(Base)) 818 // Known bases won't need new instructions introduced and can be 819 // ignored safely 820 return; 821 assert(isExpectedBDVType(Base) && "the only non-base values " 822 "we see should be base defining values"); 823 if (States.insert(std::make_pair(Base, BDVState())).second) 824 Worklist.push_back(Base); 825 }; 826 if (PHINode *PN = dyn_cast<PHINode>(Current)) { 827 for (Value *InVal : PN->incoming_values()) 828 visitIncomingValue(InVal); 829 } else if (SelectInst *SI = dyn_cast<SelectInst>(Current)) { 830 visitIncomingValue(SI->getTrueValue()); 831 visitIncomingValue(SI->getFalseValue()); 832 } else if (auto *EE = dyn_cast<ExtractElementInst>(Current)) { 833 visitIncomingValue(EE->getVectorOperand()); 834 } else if (auto *IE = dyn_cast<InsertElementInst>(Current)) { 835 visitIncomingValue(IE->getOperand(0)); // vector operand 836 visitIncomingValue(IE->getOperand(1)); // scalar operand 837 } else if (auto *SV = dyn_cast<ShuffleVectorInst>(Current)) { 838 visitIncomingValue(SV->getOperand(0)); 839 visitIncomingValue(SV->getOperand(1)); 840 } 841 else { 842 llvm_unreachable("Unimplemented instruction case"); 843 } 844 } 845 } 846 847 #ifndef NDEBUG 848 LLVM_DEBUG(dbgs() << "States after initialization:\n"); 849 for (auto Pair : States) { 850 LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n"); 851 } 852 #endif 853 854 // Return a phi state for a base defining value. We'll generate a new 855 // base state for known bases and expect to find a cached state otherwise. 856 auto getStateForBDV = [&](Value *baseValue) { 857 if (isKnownBaseResult(baseValue)) 858 return BDVState(baseValue); 859 auto I = States.find(baseValue); 860 assert(I != States.end() && "lookup failed!"); 861 return I->second; 862 }; 863 864 bool Progress = true; 865 while (Progress) { 866 #ifndef NDEBUG 867 const size_t OldSize = States.size(); 868 #endif 869 Progress = false; 870 // We're only changing values in this loop, thus safe to keep iterators. 871 // Since this is computing a fixed point, the order of visit does not 872 // effect the result. TODO: We could use a worklist here and make this run 873 // much faster. 874 for (auto Pair : States) { 875 Value *BDV = Pair.first; 876 assert(!isKnownBaseResult(BDV) && "why did it get added?"); 877 878 // Given an input value for the current instruction, return a BDVState 879 // instance which represents the BDV of that value. 880 auto getStateForInput = [&](Value *V) mutable { 881 Value *BDV = findBaseOrBDV(V, Cache); 882 return getStateForBDV(BDV); 883 }; 884 885 BDVState NewState; 886 if (SelectInst *SI = dyn_cast<SelectInst>(BDV)) { 887 NewState = meetBDVState(NewState, getStateForInput(SI->getTrueValue())); 888 NewState = 889 meetBDVState(NewState, getStateForInput(SI->getFalseValue())); 890 } else if (PHINode *PN = dyn_cast<PHINode>(BDV)) { 891 for (Value *Val : PN->incoming_values()) 892 NewState = meetBDVState(NewState, getStateForInput(Val)); 893 } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) { 894 // The 'meet' for an extractelement is slightly trivial, but it's still 895 // useful in that it drives us to conflict if our input is. 896 NewState = 897 meetBDVState(NewState, getStateForInput(EE->getVectorOperand())); 898 } else if (auto *IE = dyn_cast<InsertElementInst>(BDV)){ 899 // Given there's a inherent type mismatch between the operands, will 900 // *always* produce Conflict. 901 NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(0))); 902 NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(1))); 903 } else { 904 // The only instance this does not return a Conflict is when both the 905 // vector operands are the same vector. 906 auto *SV = cast<ShuffleVectorInst>(BDV); 907 NewState = meetBDVState(NewState, getStateForInput(SV->getOperand(0))); 908 NewState = meetBDVState(NewState, getStateForInput(SV->getOperand(1))); 909 } 910 911 BDVState OldState = States[BDV]; 912 if (OldState != NewState) { 913 Progress = true; 914 States[BDV] = NewState; 915 } 916 } 917 918 assert(OldSize == States.size() && 919 "fixed point shouldn't be adding any new nodes to state"); 920 } 921 922 #ifndef NDEBUG 923 LLVM_DEBUG(dbgs() << "States after meet iteration:\n"); 924 for (auto Pair : States) { 925 LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n"); 926 } 927 #endif 928 929 // Insert Phis for all conflicts 930 // TODO: adjust naming patterns to avoid this order of iteration dependency 931 for (auto Pair : States) { 932 Instruction *I = cast<Instruction>(Pair.first); 933 BDVState State = Pair.second; 934 assert(!isKnownBaseResult(I) && "why did it get added?"); 935 assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); 936 937 // extractelement instructions are a bit special in that we may need to 938 // insert an extract even when we know an exact base for the instruction. 939 // The problem is that we need to convert from a vector base to a scalar 940 // base for the particular indice we're interested in. 941 if (State.isBase() && isa<ExtractElementInst>(I) && 942 isa<VectorType>(State.getBaseValue()->getType())) { 943 auto *EE = cast<ExtractElementInst>(I); 944 // TODO: In many cases, the new instruction is just EE itself. We should 945 // exploit this, but can't do it here since it would break the invariant 946 // about the BDV not being known to be a base. 947 auto *BaseInst = ExtractElementInst::Create( 948 State.getBaseValue(), EE->getIndexOperand(), "base_ee", EE); 949 BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {})); 950 States[I] = BDVState(BDVState::Base, BaseInst); 951 } 952 953 // Since we're joining a vector and scalar base, they can never be the 954 // same. As a result, we should always see insert element having reached 955 // the conflict state. 956 assert(!isa<InsertElementInst>(I) || State.isConflict()); 957 958 if (!State.isConflict()) 959 continue; 960 961 /// Create and insert a new instruction which will represent the base of 962 /// the given instruction 'I'. 963 auto MakeBaseInstPlaceholder = [](Instruction *I) -> Instruction* { 964 if (isa<PHINode>(I)) { 965 BasicBlock *BB = I->getParent(); 966 int NumPreds = pred_size(BB); 967 assert(NumPreds > 0 && "how did we reach here"); 968 std::string Name = suffixed_name_or(I, ".base", "base_phi"); 969 return PHINode::Create(I->getType(), NumPreds, Name, I); 970 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) { 971 // The undef will be replaced later 972 UndefValue *Undef = UndefValue::get(SI->getType()); 973 std::string Name = suffixed_name_or(I, ".base", "base_select"); 974 return SelectInst::Create(SI->getCondition(), Undef, Undef, Name, SI); 975 } else if (auto *EE = dyn_cast<ExtractElementInst>(I)) { 976 UndefValue *Undef = UndefValue::get(EE->getVectorOperand()->getType()); 977 std::string Name = suffixed_name_or(I, ".base", "base_ee"); 978 return ExtractElementInst::Create(Undef, EE->getIndexOperand(), Name, 979 EE); 980 } else if (auto *IE = dyn_cast<InsertElementInst>(I)) { 981 UndefValue *VecUndef = UndefValue::get(IE->getOperand(0)->getType()); 982 UndefValue *ScalarUndef = UndefValue::get(IE->getOperand(1)->getType()); 983 std::string Name = suffixed_name_or(I, ".base", "base_ie"); 984 return InsertElementInst::Create(VecUndef, ScalarUndef, 985 IE->getOperand(2), Name, IE); 986 } else { 987 auto *SV = cast<ShuffleVectorInst>(I); 988 UndefValue *VecUndef = UndefValue::get(SV->getOperand(0)->getType()); 989 std::string Name = suffixed_name_or(I, ".base", "base_sv"); 990 return new ShuffleVectorInst(VecUndef, VecUndef, SV->getOperand(2), 991 Name, SV); 992 } 993 }; 994 Instruction *BaseInst = MakeBaseInstPlaceholder(I); 995 // Add metadata marking this as a base value 996 BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {})); 997 States[I] = BDVState(BDVState::Conflict, BaseInst); 998 } 999 1000 // Returns a instruction which produces the base pointer for a given 1001 // instruction. The instruction is assumed to be an input to one of the BDVs 1002 // seen in the inference algorithm above. As such, we must either already 1003 // know it's base defining value is a base, or have inserted a new 1004 // instruction to propagate the base of it's BDV and have entered that newly 1005 // introduced instruction into the state table. In either case, we are 1006 // assured to be able to determine an instruction which produces it's base 1007 // pointer. 1008 auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) { 1009 Value *BDV = findBaseOrBDV(Input, Cache); 1010 Value *Base = nullptr; 1011 if (isKnownBaseResult(BDV)) { 1012 Base = BDV; 1013 } else { 1014 // Either conflict or base. 1015 assert(States.count(BDV)); 1016 Base = States[BDV].getBaseValue(); 1017 } 1018 assert(Base && "Can't be null"); 1019 // The cast is needed since base traversal may strip away bitcasts 1020 if (Base->getType() != Input->getType() && InsertPt) 1021 Base = new BitCastInst(Base, Input->getType(), "cast", InsertPt); 1022 return Base; 1023 }; 1024 1025 // Fixup all the inputs of the new PHIs. Visit order needs to be 1026 // deterministic and predictable because we're naming newly created 1027 // instructions. 1028 for (auto Pair : States) { 1029 Instruction *BDV = cast<Instruction>(Pair.first); 1030 BDVState State = Pair.second; 1031 1032 assert(!isKnownBaseResult(BDV) && "why did it get added?"); 1033 assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); 1034 if (!State.isConflict()) 1035 continue; 1036 1037 if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) { 1038 PHINode *PN = cast<PHINode>(BDV); 1039 unsigned NumPHIValues = PN->getNumIncomingValues(); 1040 for (unsigned i = 0; i < NumPHIValues; i++) { 1041 Value *InVal = PN->getIncomingValue(i); 1042 BasicBlock *InBB = PN->getIncomingBlock(i); 1043 1044 // If we've already seen InBB, add the same incoming value 1045 // we added for it earlier. The IR verifier requires phi 1046 // nodes with multiple entries from the same basic block 1047 // to have the same incoming value for each of those 1048 // entries. If we don't do this check here and basephi 1049 // has a different type than base, we'll end up adding two 1050 // bitcasts (and hence two distinct values) as incoming 1051 // values for the same basic block. 1052 1053 int BlockIndex = BasePHI->getBasicBlockIndex(InBB); 1054 if (BlockIndex != -1) { 1055 Value *OldBase = BasePHI->getIncomingValue(BlockIndex); 1056 BasePHI->addIncoming(OldBase, InBB); 1057 1058 #ifndef NDEBUG 1059 Value *Base = getBaseForInput(InVal, nullptr); 1060 // In essence this assert states: the only way two values 1061 // incoming from the same basic block may be different is by 1062 // being different bitcasts of the same value. A cleanup 1063 // that remains TODO is changing findBaseOrBDV to return an 1064 // llvm::Value of the correct type (and still remain pure). 1065 // This will remove the need to add bitcasts. 1066 assert(Base->stripPointerCasts() == OldBase->stripPointerCasts() && 1067 "Sanity -- findBaseOrBDV should be pure!"); 1068 #endif 1069 continue; 1070 } 1071 1072 // Find the instruction which produces the base for each input. We may 1073 // need to insert a bitcast in the incoming block. 1074 // TODO: Need to split critical edges if insertion is needed 1075 Value *Base = getBaseForInput(InVal, InBB->getTerminator()); 1076 BasePHI->addIncoming(Base, InBB); 1077 } 1078 assert(BasePHI->getNumIncomingValues() == NumPHIValues); 1079 } else if (SelectInst *BaseSI = 1080 dyn_cast<SelectInst>(State.getBaseValue())) { 1081 SelectInst *SI = cast<SelectInst>(BDV); 1082 1083 // Find the instruction which produces the base for each input. 1084 // We may need to insert a bitcast. 1085 BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI)); 1086 BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI)); 1087 } else if (auto *BaseEE = 1088 dyn_cast<ExtractElementInst>(State.getBaseValue())) { 1089 Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand(); 1090 // Find the instruction which produces the base for each input. We may 1091 // need to insert a bitcast. 1092 BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE)); 1093 } else if (auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){ 1094 auto *BdvIE = cast<InsertElementInst>(BDV); 1095 auto UpdateOperand = [&](int OperandIdx) { 1096 Value *InVal = BdvIE->getOperand(OperandIdx); 1097 Value *Base = getBaseForInput(InVal, BaseIE); 1098 BaseIE->setOperand(OperandIdx, Base); 1099 }; 1100 UpdateOperand(0); // vector operand 1101 UpdateOperand(1); // scalar operand 1102 } else { 1103 auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue()); 1104 auto *BdvSV = cast<ShuffleVectorInst>(BDV); 1105 auto UpdateOperand = [&](int OperandIdx) { 1106 Value *InVal = BdvSV->getOperand(OperandIdx); 1107 Value *Base = getBaseForInput(InVal, BaseSV); 1108 BaseSV->setOperand(OperandIdx, Base); 1109 }; 1110 UpdateOperand(0); // vector operand 1111 UpdateOperand(1); // vector operand 1112 } 1113 } 1114 1115 // Cache all of our results so we can cheaply reuse them 1116 // NOTE: This is actually two caches: one of the base defining value 1117 // relation and one of the base pointer relation! FIXME 1118 for (auto Pair : States) { 1119 auto *BDV = Pair.first; 1120 Value *Base = Pair.second.getBaseValue(); 1121 assert(BDV && Base); 1122 assert(!isKnownBaseResult(BDV) && "why did it get added?"); 1123 1124 LLVM_DEBUG( 1125 dbgs() << "Updating base value cache" 1126 << " for: " << BDV->getName() << " from: " 1127 << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none") 1128 << " to: " << Base->getName() << "\n"); 1129 1130 if (Cache.count(BDV)) { 1131 assert(isKnownBaseResult(Base) && 1132 "must be something we 'know' is a base pointer"); 1133 // Once we transition from the BDV relation being store in the Cache to 1134 // the base relation being stored, it must be stable 1135 assert((!isKnownBaseResult(Cache[BDV]) || Cache[BDV] == Base) && 1136 "base relation should be stable"); 1137 } 1138 Cache[BDV] = Base; 1139 } 1140 assert(Cache.count(Def)); 1141 return Cache[Def]; 1142 } 1143 1144 // For a set of live pointers (base and/or derived), identify the base 1145 // pointer of the object which they are derived from. This routine will 1146 // mutate the IR graph as needed to make the 'base' pointer live at the 1147 // definition site of 'derived'. This ensures that any use of 'derived' can 1148 // also use 'base'. This may involve the insertion of a number of 1149 // additional PHI nodes. 1150 // 1151 // preconditions: live is a set of pointer type Values 1152 // 1153 // side effects: may insert PHI nodes into the existing CFG, will preserve 1154 // CFG, will not remove or mutate any existing nodes 1155 // 1156 // post condition: PointerToBase contains one (derived, base) pair for every 1157 // pointer in live. Note that derived can be equal to base if the original 1158 // pointer was a base pointer. 1159 static void 1160 findBasePointers(const StatepointLiveSetTy &live, 1161 MapVector<Value *, Value *> &PointerToBase, 1162 DominatorTree *DT, DefiningValueMapTy &DVCache) { 1163 for (Value *ptr : live) { 1164 Value *base = findBasePointer(ptr, DVCache); 1165 assert(base && "failed to find base pointer"); 1166 PointerToBase[ptr] = base; 1167 assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) || 1168 DT->dominates(cast<Instruction>(base)->getParent(), 1169 cast<Instruction>(ptr)->getParent())) && 1170 "The base we found better dominate the derived pointer"); 1171 } 1172 } 1173 1174 /// Find the required based pointers (and adjust the live set) for the given 1175 /// parse point. 1176 static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache, 1177 CallBase *Call, 1178 PartiallyConstructedSafepointRecord &result) { 1179 MapVector<Value *, Value *> PointerToBase; 1180 findBasePointers(result.LiveSet, PointerToBase, &DT, DVCache); 1181 1182 if (PrintBasePointers) { 1183 errs() << "Base Pairs (w/o Relocation):\n"; 1184 for (auto &Pair : PointerToBase) { 1185 errs() << " derived "; 1186 Pair.first->printAsOperand(errs(), false); 1187 errs() << " base "; 1188 Pair.second->printAsOperand(errs(), false); 1189 errs() << "\n";; 1190 } 1191 } 1192 1193 result.PointerToBase = PointerToBase; 1194 } 1195 1196 /// Given an updated version of the dataflow liveness results, update the 1197 /// liveset and base pointer maps for the call site CS. 1198 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, 1199 CallBase *Call, 1200 PartiallyConstructedSafepointRecord &result); 1201 1202 static void recomputeLiveInValues( 1203 Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate, 1204 MutableArrayRef<struct PartiallyConstructedSafepointRecord> records) { 1205 // TODO-PERF: reuse the original liveness, then simply run the dataflow 1206 // again. The old values are still live and will help it stabilize quickly. 1207 GCPtrLivenessData RevisedLivenessData; 1208 computeLiveInValues(DT, F, RevisedLivenessData); 1209 for (size_t i = 0; i < records.size(); i++) { 1210 struct PartiallyConstructedSafepointRecord &info = records[i]; 1211 recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info); 1212 } 1213 } 1214 1215 // When inserting gc.relocate and gc.result calls, we need to ensure there are 1216 // no uses of the original value / return value between the gc.statepoint and 1217 // the gc.relocate / gc.result call. One case which can arise is a phi node 1218 // starting one of the successor blocks. We also need to be able to insert the 1219 // gc.relocates only on the path which goes through the statepoint. We might 1220 // need to split an edge to make this possible. 1221 static BasicBlock * 1222 normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent, 1223 DominatorTree &DT) { 1224 BasicBlock *Ret = BB; 1225 if (!BB->getUniquePredecessor()) 1226 Ret = SplitBlockPredecessors(BB, InvokeParent, "", &DT); 1227 1228 // Now that 'Ret' has unique predecessor we can safely remove all phi nodes 1229 // from it 1230 FoldSingleEntryPHINodes(Ret); 1231 assert(!isa<PHINode>(Ret->begin()) && 1232 "All PHI nodes should have been removed!"); 1233 1234 // At this point, we can safely insert a gc.relocate or gc.result as the first 1235 // instruction in Ret if needed. 1236 return Ret; 1237 } 1238 1239 // Create new attribute set containing only attributes which can be transferred 1240 // from original call to the safepoint. 1241 static AttributeList legalizeCallAttributes(AttributeList AL) { 1242 if (AL.isEmpty()) 1243 return AL; 1244 1245 // Remove the readonly, readnone, and statepoint function attributes. 1246 AttrBuilder FnAttrs = AL.getFnAttributes(); 1247 FnAttrs.removeAttribute(Attribute::ReadNone); 1248 FnAttrs.removeAttribute(Attribute::ReadOnly); 1249 for (Attribute A : AL.getFnAttributes()) { 1250 if (isStatepointDirectiveAttr(A)) 1251 FnAttrs.remove(A); 1252 } 1253 1254 // Just skip parameter and return attributes for now 1255 LLVMContext &Ctx = AL.getContext(); 1256 return AttributeList::get(Ctx, AttributeList::FunctionIndex, 1257 AttributeSet::get(Ctx, FnAttrs)); 1258 } 1259 1260 /// Helper function to place all gc relocates necessary for the given 1261 /// statepoint. 1262 /// Inputs: 1263 /// liveVariables - list of variables to be relocated. 1264 /// liveStart - index of the first live variable. 1265 /// basePtrs - base pointers. 1266 /// statepointToken - statepoint instruction to which relocates should be 1267 /// bound. 1268 /// Builder - Llvm IR builder to be used to construct new calls. 1269 static void CreateGCRelocates(ArrayRef<Value *> LiveVariables, 1270 const int LiveStart, 1271 ArrayRef<Value *> BasePtrs, 1272 Instruction *StatepointToken, 1273 IRBuilder<> Builder) { 1274 if (LiveVariables.empty()) 1275 return; 1276 1277 auto FindIndex = [](ArrayRef<Value *> LiveVec, Value *Val) { 1278 auto ValIt = llvm::find(LiveVec, Val); 1279 assert(ValIt != LiveVec.end() && "Val not found in LiveVec!"); 1280 size_t Index = std::distance(LiveVec.begin(), ValIt); 1281 assert(Index < LiveVec.size() && "Bug in std::find?"); 1282 return Index; 1283 }; 1284 Module *M = StatepointToken->getModule(); 1285 1286 // All gc_relocate are generated as i8 addrspace(1)* (or a vector type whose 1287 // element type is i8 addrspace(1)*). We originally generated unique 1288 // declarations for each pointer type, but this proved problematic because 1289 // the intrinsic mangling code is incomplete and fragile. Since we're moving 1290 // towards a single unified pointer type anyways, we can just cast everything 1291 // to an i8* of the right address space. A bitcast is added later to convert 1292 // gc_relocate to the actual value's type. 1293 auto getGCRelocateDecl = [&] (Type *Ty) { 1294 assert(isHandledGCPointerType(Ty)); 1295 auto AS = Ty->getScalarType()->getPointerAddressSpace(); 1296 Type *NewTy = Type::getInt8PtrTy(M->getContext(), AS); 1297 if (auto *VT = dyn_cast<VectorType>(Ty)) 1298 NewTy = VectorType::get(NewTy, VT->getNumElements()); 1299 return Intrinsic::getDeclaration(M, Intrinsic::experimental_gc_relocate, 1300 {NewTy}); 1301 }; 1302 1303 // Lazily populated map from input types to the canonicalized form mentioned 1304 // in the comment above. This should probably be cached somewhere more 1305 // broadly. 1306 DenseMap<Type *, Function *> TypeToDeclMap; 1307 1308 for (unsigned i = 0; i < LiveVariables.size(); i++) { 1309 // Generate the gc.relocate call and save the result 1310 Value *BaseIdx = 1311 Builder.getInt32(LiveStart + FindIndex(LiveVariables, BasePtrs[i])); 1312 Value *LiveIdx = Builder.getInt32(LiveStart + i); 1313 1314 Type *Ty = LiveVariables[i]->getType(); 1315 if (!TypeToDeclMap.count(Ty)) 1316 TypeToDeclMap[Ty] = getGCRelocateDecl(Ty); 1317 Function *GCRelocateDecl = TypeToDeclMap[Ty]; 1318 1319 // only specify a debug name if we can give a useful one 1320 CallInst *Reloc = Builder.CreateCall( 1321 GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx}, 1322 suffixed_name_or(LiveVariables[i], ".relocated", "")); 1323 // Trick CodeGen into thinking there are lots of free registers at this 1324 // fake call. 1325 Reloc->setCallingConv(CallingConv::Cold); 1326 } 1327 } 1328 1329 namespace { 1330 1331 /// This struct is used to defer RAUWs and `eraseFromParent` s. Using this 1332 /// avoids having to worry about keeping around dangling pointers to Values. 1333 class DeferredReplacement { 1334 AssertingVH<Instruction> Old; 1335 AssertingVH<Instruction> New; 1336 bool IsDeoptimize = false; 1337 1338 DeferredReplacement() = default; 1339 1340 public: 1341 static DeferredReplacement createRAUW(Instruction *Old, Instruction *New) { 1342 assert(Old != New && Old && New && 1343 "Cannot RAUW equal values or to / from null!"); 1344 1345 DeferredReplacement D; 1346 D.Old = Old; 1347 D.New = New; 1348 return D; 1349 } 1350 1351 static DeferredReplacement createDelete(Instruction *ToErase) { 1352 DeferredReplacement D; 1353 D.Old = ToErase; 1354 return D; 1355 } 1356 1357 static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) { 1358 #ifndef NDEBUG 1359 auto *F = cast<CallInst>(Old)->getCalledFunction(); 1360 assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize && 1361 "Only way to construct a deoptimize deferred replacement"); 1362 #endif 1363 DeferredReplacement D; 1364 D.Old = Old; 1365 D.IsDeoptimize = true; 1366 return D; 1367 } 1368 1369 /// Does the task represented by this instance. 1370 void doReplacement() { 1371 Instruction *OldI = Old; 1372 Instruction *NewI = New; 1373 1374 assert(OldI != NewI && "Disallowed at construction?!"); 1375 assert((!IsDeoptimize || !New) && 1376 "Deoptimize intrinsics are not replaced!"); 1377 1378 Old = nullptr; 1379 New = nullptr; 1380 1381 if (NewI) 1382 OldI->replaceAllUsesWith(NewI); 1383 1384 if (IsDeoptimize) { 1385 // Note: we've inserted instructions, so the call to llvm.deoptimize may 1386 // not necessarily be followed by the matching return. 1387 auto *RI = cast<ReturnInst>(OldI->getParent()->getTerminator()); 1388 new UnreachableInst(RI->getContext(), RI); 1389 RI->eraseFromParent(); 1390 } 1391 1392 OldI->eraseFromParent(); 1393 } 1394 }; 1395 1396 } // end anonymous namespace 1397 1398 static StringRef getDeoptLowering(CallBase *Call) { 1399 const char *DeoptLowering = "deopt-lowering"; 1400 if (Call->hasFnAttr(DeoptLowering)) { 1401 // FIXME: Calls have a *really* confusing interface around attributes 1402 // with values. 1403 const AttributeList &CSAS = Call->getAttributes(); 1404 if (CSAS.hasAttribute(AttributeList::FunctionIndex, DeoptLowering)) 1405 return CSAS.getAttribute(AttributeList::FunctionIndex, DeoptLowering) 1406 .getValueAsString(); 1407 Function *F = Call->getCalledFunction(); 1408 assert(F && F->hasFnAttribute(DeoptLowering)); 1409 return F->getFnAttribute(DeoptLowering).getValueAsString(); 1410 } 1411 return "live-through"; 1412 } 1413 1414 static void 1415 makeStatepointExplicitImpl(CallBase *Call, /* to replace */ 1416 const SmallVectorImpl<Value *> &BasePtrs, 1417 const SmallVectorImpl<Value *> &LiveVariables, 1418 PartiallyConstructedSafepointRecord &Result, 1419 std::vector<DeferredReplacement> &Replacements) { 1420 assert(BasePtrs.size() == LiveVariables.size()); 1421 1422 // Then go ahead and use the builder do actually do the inserts. We insert 1423 // immediately before the previous instruction under the assumption that all 1424 // arguments will be available here. We can't insert afterwards since we may 1425 // be replacing a terminator. 1426 IRBuilder<> Builder(Call); 1427 1428 ArrayRef<Value *> GCArgs(LiveVariables); 1429 uint64_t StatepointID = StatepointDirectives::DefaultStatepointID; 1430 uint32_t NumPatchBytes = 0; 1431 uint32_t Flags = uint32_t(StatepointFlags::None); 1432 1433 ArrayRef<Use> CallArgs(Call->arg_begin(), Call->arg_end()); 1434 ArrayRef<Use> DeoptArgs = GetDeoptBundleOperands(Call); 1435 ArrayRef<Use> TransitionArgs; 1436 if (auto TransitionBundle = 1437 Call->getOperandBundle(LLVMContext::OB_gc_transition)) { 1438 Flags |= uint32_t(StatepointFlags::GCTransition); 1439 TransitionArgs = TransitionBundle->Inputs; 1440 } 1441 1442 // Instead of lowering calls to @llvm.experimental.deoptimize as normal calls 1443 // with a return value, we lower then as never returning calls to 1444 // __llvm_deoptimize that are followed by unreachable to get better codegen. 1445 bool IsDeoptimize = false; 1446 1447 StatepointDirectives SD = 1448 parseStatepointDirectivesFromAttrs(Call->getAttributes()); 1449 if (SD.NumPatchBytes) 1450 NumPatchBytes = *SD.NumPatchBytes; 1451 if (SD.StatepointID) 1452 StatepointID = *SD.StatepointID; 1453 1454 // Pass through the requested lowering if any. The default is live-through. 1455 StringRef DeoptLowering = getDeoptLowering(Call); 1456 if (DeoptLowering.equals("live-in")) 1457 Flags |= uint32_t(StatepointFlags::DeoptLiveIn); 1458 else { 1459 assert(DeoptLowering.equals("live-through") && "Unsupported value!"); 1460 } 1461 1462 Value *CallTarget = Call->getCalledValue(); 1463 if (Function *F = dyn_cast<Function>(CallTarget)) { 1464 if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize) { 1465 // Calls to llvm.experimental.deoptimize are lowered to calls to the 1466 // __llvm_deoptimize symbol. We want to resolve this now, since the 1467 // verifier does not allow taking the address of an intrinsic function. 1468 1469 SmallVector<Type *, 8> DomainTy; 1470 for (Value *Arg : CallArgs) 1471 DomainTy.push_back(Arg->getType()); 1472 auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy, 1473 /* isVarArg = */ false); 1474 1475 // Note: CallTarget can be a bitcast instruction of a symbol if there are 1476 // calls to @llvm.experimental.deoptimize with different argument types in 1477 // the same module. This is fine -- we assume the frontend knew what it 1478 // was doing when generating this kind of IR. 1479 CallTarget = F->getParent() 1480 ->getOrInsertFunction("__llvm_deoptimize", FTy) 1481 .getCallee(); 1482 1483 IsDeoptimize = true; 1484 } 1485 } 1486 1487 // Create the statepoint given all the arguments 1488 Instruction *Token = nullptr; 1489 if (auto *CI = dyn_cast<CallInst>(Call)) { 1490 CallInst *SPCall = Builder.CreateGCStatepointCall( 1491 StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs, 1492 TransitionArgs, DeoptArgs, GCArgs, "safepoint_token"); 1493 1494 SPCall->setTailCallKind(CI->getTailCallKind()); 1495 SPCall->setCallingConv(CI->getCallingConv()); 1496 1497 // Currently we will fail on parameter attributes and on certain 1498 // function attributes. In case if we can handle this set of attributes - 1499 // set up function attrs directly on statepoint and return attrs later for 1500 // gc_result intrinsic. 1501 SPCall->setAttributes(legalizeCallAttributes(CI->getAttributes())); 1502 1503 Token = SPCall; 1504 1505 // Put the following gc_result and gc_relocate calls immediately after the 1506 // the old call (which we're about to delete) 1507 assert(CI->getNextNode() && "Not a terminator, must have next!"); 1508 Builder.SetInsertPoint(CI->getNextNode()); 1509 Builder.SetCurrentDebugLocation(CI->getNextNode()->getDebugLoc()); 1510 } else { 1511 auto *II = cast<InvokeInst>(Call); 1512 1513 // Insert the new invoke into the old block. We'll remove the old one in a 1514 // moment at which point this will become the new terminator for the 1515 // original block. 1516 InvokeInst *SPInvoke = Builder.CreateGCStatepointInvoke( 1517 StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(), 1518 II->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs, GCArgs, 1519 "statepoint_token"); 1520 1521 SPInvoke->setCallingConv(II->getCallingConv()); 1522 1523 // Currently we will fail on parameter attributes and on certain 1524 // function attributes. In case if we can handle this set of attributes - 1525 // set up function attrs directly on statepoint and return attrs later for 1526 // gc_result intrinsic. 1527 SPInvoke->setAttributes(legalizeCallAttributes(II->getAttributes())); 1528 1529 Token = SPInvoke; 1530 1531 // Generate gc relocates in exceptional path 1532 BasicBlock *UnwindBlock = II->getUnwindDest(); 1533 assert(!isa<PHINode>(UnwindBlock->begin()) && 1534 UnwindBlock->getUniquePredecessor() && 1535 "can't safely insert in this block!"); 1536 1537 Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt()); 1538 Builder.SetCurrentDebugLocation(II->getDebugLoc()); 1539 1540 // Attach exceptional gc relocates to the landingpad. 1541 Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst(); 1542 Result.UnwindToken = ExceptionalToken; 1543 1544 const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx(); 1545 CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, ExceptionalToken, 1546 Builder); 1547 1548 // Generate gc relocates and returns for normal block 1549 BasicBlock *NormalDest = II->getNormalDest(); 1550 assert(!isa<PHINode>(NormalDest->begin()) && 1551 NormalDest->getUniquePredecessor() && 1552 "can't safely insert in this block!"); 1553 1554 Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt()); 1555 1556 // gc relocates will be generated later as if it were regular call 1557 // statepoint 1558 } 1559 assert(Token && "Should be set in one of the above branches!"); 1560 1561 if (IsDeoptimize) { 1562 // If we're wrapping an @llvm.experimental.deoptimize in a statepoint, we 1563 // transform the tail-call like structure to a call to a void function 1564 // followed by unreachable to get better codegen. 1565 Replacements.push_back( 1566 DeferredReplacement::createDeoptimizeReplacement(Call)); 1567 } else { 1568 Token->setName("statepoint_token"); 1569 if (!Call->getType()->isVoidTy() && !Call->use_empty()) { 1570 StringRef Name = Call->hasName() ? Call->getName() : ""; 1571 CallInst *GCResult = Builder.CreateGCResult(Token, Call->getType(), Name); 1572 GCResult->setAttributes( 1573 AttributeList::get(GCResult->getContext(), AttributeList::ReturnIndex, 1574 Call->getAttributes().getRetAttributes())); 1575 1576 // We cannot RAUW or delete CS.getInstruction() because it could be in the 1577 // live set of some other safepoint, in which case that safepoint's 1578 // PartiallyConstructedSafepointRecord will hold a raw pointer to this 1579 // llvm::Instruction. Instead, we defer the replacement and deletion to 1580 // after the live sets have been made explicit in the IR, and we no longer 1581 // have raw pointers to worry about. 1582 Replacements.emplace_back( 1583 DeferredReplacement::createRAUW(Call, GCResult)); 1584 } else { 1585 Replacements.emplace_back(DeferredReplacement::createDelete(Call)); 1586 } 1587 } 1588 1589 Result.StatepointToken = Token; 1590 1591 // Second, create a gc.relocate for every live variable 1592 const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx(); 1593 CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder); 1594 } 1595 1596 // Replace an existing gc.statepoint with a new one and a set of gc.relocates 1597 // which make the relocations happening at this safepoint explicit. 1598 // 1599 // WARNING: Does not do any fixup to adjust users of the original live 1600 // values. That's the callers responsibility. 1601 static void 1602 makeStatepointExplicit(DominatorTree &DT, CallBase *Call, 1603 PartiallyConstructedSafepointRecord &Result, 1604 std::vector<DeferredReplacement> &Replacements) { 1605 const auto &LiveSet = Result.LiveSet; 1606 const auto &PointerToBase = Result.PointerToBase; 1607 1608 // Convert to vector for efficient cross referencing. 1609 SmallVector<Value *, 64> BaseVec, LiveVec; 1610 LiveVec.reserve(LiveSet.size()); 1611 BaseVec.reserve(LiveSet.size()); 1612 for (Value *L : LiveSet) { 1613 LiveVec.push_back(L); 1614 assert(PointerToBase.count(L)); 1615 Value *Base = PointerToBase.find(L)->second; 1616 BaseVec.push_back(Base); 1617 } 1618 assert(LiveVec.size() == BaseVec.size()); 1619 1620 // Do the actual rewriting and delete the old statepoint 1621 makeStatepointExplicitImpl(Call, BaseVec, LiveVec, Result, Replacements); 1622 } 1623 1624 // Helper function for the relocationViaAlloca. 1625 // 1626 // It receives iterator to the statepoint gc relocates and emits a store to the 1627 // assigned location (via allocaMap) for the each one of them. It adds the 1628 // visited values into the visitedLiveValues set, which we will later use them 1629 // for sanity checking. 1630 static void 1631 insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs, 1632 DenseMap<Value *, AllocaInst *> &AllocaMap, 1633 DenseSet<Value *> &VisitedLiveValues) { 1634 for (User *U : GCRelocs) { 1635 GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U); 1636 if (!Relocate) 1637 continue; 1638 1639 Value *OriginalValue = Relocate->getDerivedPtr(); 1640 assert(AllocaMap.count(OriginalValue)); 1641 Value *Alloca = AllocaMap[OriginalValue]; 1642 1643 // Emit store into the related alloca 1644 // All gc_relocates are i8 addrspace(1)* typed, and it must be bitcasted to 1645 // the correct type according to alloca. 1646 assert(Relocate->getNextNode() && 1647 "Should always have one since it's not a terminator"); 1648 IRBuilder<> Builder(Relocate->getNextNode()); 1649 Value *CastedRelocatedValue = 1650 Builder.CreateBitCast(Relocate, 1651 cast<AllocaInst>(Alloca)->getAllocatedType(), 1652 suffixed_name_or(Relocate, ".casted", "")); 1653 1654 StoreInst *Store = new StoreInst(CastedRelocatedValue, Alloca); 1655 Store->insertAfter(cast<Instruction>(CastedRelocatedValue)); 1656 1657 #ifndef NDEBUG 1658 VisitedLiveValues.insert(OriginalValue); 1659 #endif 1660 } 1661 } 1662 1663 // Helper function for the "relocationViaAlloca". Similar to the 1664 // "insertRelocationStores" but works for rematerialized values. 1665 static void insertRematerializationStores( 1666 const RematerializedValueMapTy &RematerializedValues, 1667 DenseMap<Value *, AllocaInst *> &AllocaMap, 1668 DenseSet<Value *> &VisitedLiveValues) { 1669 for (auto RematerializedValuePair: RematerializedValues) { 1670 Instruction *RematerializedValue = RematerializedValuePair.first; 1671 Value *OriginalValue = RematerializedValuePair.second; 1672 1673 assert(AllocaMap.count(OriginalValue) && 1674 "Can not find alloca for rematerialized value"); 1675 Value *Alloca = AllocaMap[OriginalValue]; 1676 1677 StoreInst *Store = new StoreInst(RematerializedValue, Alloca); 1678 Store->insertAfter(RematerializedValue); 1679 1680 #ifndef NDEBUG 1681 VisitedLiveValues.insert(OriginalValue); 1682 #endif 1683 } 1684 } 1685 1686 /// Do all the relocation update via allocas and mem2reg 1687 static void relocationViaAlloca( 1688 Function &F, DominatorTree &DT, ArrayRef<Value *> Live, 1689 ArrayRef<PartiallyConstructedSafepointRecord> Records) { 1690 #ifndef NDEBUG 1691 // record initial number of (static) allocas; we'll check we have the same 1692 // number when we get done. 1693 int InitialAllocaNum = 0; 1694 for (Instruction &I : F.getEntryBlock()) 1695 if (isa<AllocaInst>(I)) 1696 InitialAllocaNum++; 1697 #endif 1698 1699 // TODO-PERF: change data structures, reserve 1700 DenseMap<Value *, AllocaInst *> AllocaMap; 1701 SmallVector<AllocaInst *, 200> PromotableAllocas; 1702 // Used later to chack that we have enough allocas to store all values 1703 std::size_t NumRematerializedValues = 0; 1704 PromotableAllocas.reserve(Live.size()); 1705 1706 // Emit alloca for "LiveValue" and record it in "allocaMap" and 1707 // "PromotableAllocas" 1708 const DataLayout &DL = F.getParent()->getDataLayout(); 1709 auto emitAllocaFor = [&](Value *LiveValue) { 1710 AllocaInst *Alloca = new AllocaInst(LiveValue->getType(), 1711 DL.getAllocaAddrSpace(), "", 1712 F.getEntryBlock().getFirstNonPHI()); 1713 AllocaMap[LiveValue] = Alloca; 1714 PromotableAllocas.push_back(Alloca); 1715 }; 1716 1717 // Emit alloca for each live gc pointer 1718 for (Value *V : Live) 1719 emitAllocaFor(V); 1720 1721 // Emit allocas for rematerialized values 1722 for (const auto &Info : Records) 1723 for (auto RematerializedValuePair : Info.RematerializedValues) { 1724 Value *OriginalValue = RematerializedValuePair.second; 1725 if (AllocaMap.count(OriginalValue) != 0) 1726 continue; 1727 1728 emitAllocaFor(OriginalValue); 1729 ++NumRematerializedValues; 1730 } 1731 1732 // The next two loops are part of the same conceptual operation. We need to 1733 // insert a store to the alloca after the original def and at each 1734 // redefinition. We need to insert a load before each use. These are split 1735 // into distinct loops for performance reasons. 1736 1737 // Update gc pointer after each statepoint: either store a relocated value or 1738 // null (if no relocated value was found for this gc pointer and it is not a 1739 // gc_result). This must happen before we update the statepoint with load of 1740 // alloca otherwise we lose the link between statepoint and old def. 1741 for (const auto &Info : Records) { 1742 Value *Statepoint = Info.StatepointToken; 1743 1744 // This will be used for consistency check 1745 DenseSet<Value *> VisitedLiveValues; 1746 1747 // Insert stores for normal statepoint gc relocates 1748 insertRelocationStores(Statepoint->users(), AllocaMap, VisitedLiveValues); 1749 1750 // In case if it was invoke statepoint 1751 // we will insert stores for exceptional path gc relocates. 1752 if (isa<InvokeInst>(Statepoint)) { 1753 insertRelocationStores(Info.UnwindToken->users(), AllocaMap, 1754 VisitedLiveValues); 1755 } 1756 1757 // Do similar thing with rematerialized values 1758 insertRematerializationStores(Info.RematerializedValues, AllocaMap, 1759 VisitedLiveValues); 1760 1761 if (ClobberNonLive) { 1762 // As a debugging aid, pretend that an unrelocated pointer becomes null at 1763 // the gc.statepoint. This will turn some subtle GC problems into 1764 // slightly easier to debug SEGVs. Note that on large IR files with 1765 // lots of gc.statepoints this is extremely costly both memory and time 1766 // wise. 1767 SmallVector<AllocaInst *, 64> ToClobber; 1768 for (auto Pair : AllocaMap) { 1769 Value *Def = Pair.first; 1770 AllocaInst *Alloca = Pair.second; 1771 1772 // This value was relocated 1773 if (VisitedLiveValues.count(Def)) { 1774 continue; 1775 } 1776 ToClobber.push_back(Alloca); 1777 } 1778 1779 auto InsertClobbersAt = [&](Instruction *IP) { 1780 for (auto *AI : ToClobber) { 1781 auto PT = cast<PointerType>(AI->getAllocatedType()); 1782 Constant *CPN = ConstantPointerNull::get(PT); 1783 StoreInst *Store = new StoreInst(CPN, AI); 1784 Store->insertBefore(IP); 1785 } 1786 }; 1787 1788 // Insert the clobbering stores. These may get intermixed with the 1789 // gc.results and gc.relocates, but that's fine. 1790 if (auto II = dyn_cast<InvokeInst>(Statepoint)) { 1791 InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt()); 1792 InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt()); 1793 } else { 1794 InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode()); 1795 } 1796 } 1797 } 1798 1799 // Update use with load allocas and add store for gc_relocated. 1800 for (auto Pair : AllocaMap) { 1801 Value *Def = Pair.first; 1802 AllocaInst *Alloca = Pair.second; 1803 1804 // We pre-record the uses of allocas so that we dont have to worry about 1805 // later update that changes the user information.. 1806 1807 SmallVector<Instruction *, 20> Uses; 1808 // PERF: trade a linear scan for repeated reallocation 1809 Uses.reserve(Def->getNumUses()); 1810 for (User *U : Def->users()) { 1811 if (!isa<ConstantExpr>(U)) { 1812 // If the def has a ConstantExpr use, then the def is either a 1813 // ConstantExpr use itself or null. In either case 1814 // (recursively in the first, directly in the second), the oop 1815 // it is ultimately dependent on is null and this particular 1816 // use does not need to be fixed up. 1817 Uses.push_back(cast<Instruction>(U)); 1818 } 1819 } 1820 1821 llvm::sort(Uses); 1822 auto Last = std::unique(Uses.begin(), Uses.end()); 1823 Uses.erase(Last, Uses.end()); 1824 1825 for (Instruction *Use : Uses) { 1826 if (isa<PHINode>(Use)) { 1827 PHINode *Phi = cast<PHINode>(Use); 1828 for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) { 1829 if (Def == Phi->getIncomingValue(i)) { 1830 LoadInst *Load = 1831 new LoadInst(Alloca->getAllocatedType(), Alloca, "", 1832 Phi->getIncomingBlock(i)->getTerminator()); 1833 Phi->setIncomingValue(i, Load); 1834 } 1835 } 1836 } else { 1837 LoadInst *Load = 1838 new LoadInst(Alloca->getAllocatedType(), Alloca, "", Use); 1839 Use->replaceUsesOfWith(Def, Load); 1840 } 1841 } 1842 1843 // Emit store for the initial gc value. Store must be inserted after load, 1844 // otherwise store will be in alloca's use list and an extra load will be 1845 // inserted before it. 1846 StoreInst *Store = new StoreInst(Def, Alloca); 1847 if (Instruction *Inst = dyn_cast<Instruction>(Def)) { 1848 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) { 1849 // InvokeInst is a terminator so the store need to be inserted into its 1850 // normal destination block. 1851 BasicBlock *NormalDest = Invoke->getNormalDest(); 1852 Store->insertBefore(NormalDest->getFirstNonPHI()); 1853 } else { 1854 assert(!Inst->isTerminator() && 1855 "The only terminator that can produce a value is " 1856 "InvokeInst which is handled above."); 1857 Store->insertAfter(Inst); 1858 } 1859 } else { 1860 assert(isa<Argument>(Def)); 1861 Store->insertAfter(cast<Instruction>(Alloca)); 1862 } 1863 } 1864 1865 assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues && 1866 "we must have the same allocas with lives"); 1867 if (!PromotableAllocas.empty()) { 1868 // Apply mem2reg to promote alloca to SSA 1869 PromoteMemToReg(PromotableAllocas, DT); 1870 } 1871 1872 #ifndef NDEBUG 1873 for (auto &I : F.getEntryBlock()) 1874 if (isa<AllocaInst>(I)) 1875 InitialAllocaNum--; 1876 assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas"); 1877 #endif 1878 } 1879 1880 /// Implement a unique function which doesn't require we sort the input 1881 /// vector. Doing so has the effect of changing the output of a couple of 1882 /// tests in ways which make them less useful in testing fused safepoints. 1883 template <typename T> static void unique_unsorted(SmallVectorImpl<T> &Vec) { 1884 SmallSet<T, 8> Seen; 1885 Vec.erase(remove_if(Vec, [&](const T &V) { return !Seen.insert(V).second; }), 1886 Vec.end()); 1887 } 1888 1889 /// Insert holders so that each Value is obviously live through the entire 1890 /// lifetime of the call. 1891 static void insertUseHolderAfter(CallBase *Call, const ArrayRef<Value *> Values, 1892 SmallVectorImpl<CallInst *> &Holders) { 1893 if (Values.empty()) 1894 // No values to hold live, might as well not insert the empty holder 1895 return; 1896 1897 Module *M = Call->getModule(); 1898 // Use a dummy vararg function to actually hold the values live 1899 FunctionCallee Func = M->getOrInsertFunction( 1900 "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true)); 1901 if (isa<CallInst>(Call)) { 1902 // For call safepoints insert dummy calls right after safepoint 1903 Holders.push_back( 1904 CallInst::Create(Func, Values, "", &*++Call->getIterator())); 1905 return; 1906 } 1907 // For invoke safepooints insert dummy calls both in normal and 1908 // exceptional destination blocks 1909 auto *II = cast<InvokeInst>(Call); 1910 Holders.push_back(CallInst::Create( 1911 Func, Values, "", &*II->getNormalDest()->getFirstInsertionPt())); 1912 Holders.push_back(CallInst::Create( 1913 Func, Values, "", &*II->getUnwindDest()->getFirstInsertionPt())); 1914 } 1915 1916 static void findLiveReferences( 1917 Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate, 1918 MutableArrayRef<struct PartiallyConstructedSafepointRecord> records) { 1919 GCPtrLivenessData OriginalLivenessData; 1920 computeLiveInValues(DT, F, OriginalLivenessData); 1921 for (size_t i = 0; i < records.size(); i++) { 1922 struct PartiallyConstructedSafepointRecord &info = records[i]; 1923 analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info); 1924 } 1925 } 1926 1927 // Helper function for the "rematerializeLiveValues". It walks use chain 1928 // starting from the "CurrentValue" until it reaches the root of the chain, i.e. 1929 // the base or a value it cannot process. Only "simple" values are processed 1930 // (currently it is GEP's and casts). The returned root is examined by the 1931 // callers of findRematerializableChainToBasePointer. Fills "ChainToBase" array 1932 // with all visited values. 1933 static Value* findRematerializableChainToBasePointer( 1934 SmallVectorImpl<Instruction*> &ChainToBase, 1935 Value *CurrentValue) { 1936 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) { 1937 ChainToBase.push_back(GEP); 1938 return findRematerializableChainToBasePointer(ChainToBase, 1939 GEP->getPointerOperand()); 1940 } 1941 1942 if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) { 1943 if (!CI->isNoopCast(CI->getModule()->getDataLayout())) 1944 return CI; 1945 1946 ChainToBase.push_back(CI); 1947 return findRematerializableChainToBasePointer(ChainToBase, 1948 CI->getOperand(0)); 1949 } 1950 1951 // We have reached the root of the chain, which is either equal to the base or 1952 // is the first unsupported value along the use chain. 1953 return CurrentValue; 1954 } 1955 1956 // Helper function for the "rematerializeLiveValues". Compute cost of the use 1957 // chain we are going to rematerialize. 1958 static unsigned 1959 chainToBasePointerCost(SmallVectorImpl<Instruction*> &Chain, 1960 TargetTransformInfo &TTI) { 1961 unsigned Cost = 0; 1962 1963 for (Instruction *Instr : Chain) { 1964 if (CastInst *CI = dyn_cast<CastInst>(Instr)) { 1965 assert(CI->isNoopCast(CI->getModule()->getDataLayout()) && 1966 "non noop cast is found during rematerialization"); 1967 1968 Type *SrcTy = CI->getOperand(0)->getType(); 1969 Cost += TTI.getCastInstrCost(CI->getOpcode(), CI->getType(), SrcTy, CI); 1970 1971 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) { 1972 // Cost of the address calculation 1973 Type *ValTy = GEP->getSourceElementType(); 1974 Cost += TTI.getAddressComputationCost(ValTy); 1975 1976 // And cost of the GEP itself 1977 // TODO: Use TTI->getGEPCost here (it exists, but appears to be not 1978 // allowed for the external usage) 1979 if (!GEP->hasAllConstantIndices()) 1980 Cost += 2; 1981 1982 } else { 1983 llvm_unreachable("unsupported instruction type during rematerialization"); 1984 } 1985 } 1986 1987 return Cost; 1988 } 1989 1990 static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi) { 1991 unsigned PhiNum = OrigRootPhi.getNumIncomingValues(); 1992 if (PhiNum != AlternateRootPhi.getNumIncomingValues() || 1993 OrigRootPhi.getParent() != AlternateRootPhi.getParent()) 1994 return false; 1995 // Map of incoming values and their corresponding basic blocks of 1996 // OrigRootPhi. 1997 SmallDenseMap<Value *, BasicBlock *, 8> CurrentIncomingValues; 1998 for (unsigned i = 0; i < PhiNum; i++) 1999 CurrentIncomingValues[OrigRootPhi.getIncomingValue(i)] = 2000 OrigRootPhi.getIncomingBlock(i); 2001 2002 // Both current and base PHIs should have same incoming values and 2003 // the same basic blocks corresponding to the incoming values. 2004 for (unsigned i = 0; i < PhiNum; i++) { 2005 auto CIVI = 2006 CurrentIncomingValues.find(AlternateRootPhi.getIncomingValue(i)); 2007 if (CIVI == CurrentIncomingValues.end()) 2008 return false; 2009 BasicBlock *CurrentIncomingBB = CIVI->second; 2010 if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i)) 2011 return false; 2012 } 2013 return true; 2014 } 2015 2016 // From the statepoint live set pick values that are cheaper to recompute then 2017 // to relocate. Remove this values from the live set, rematerialize them after 2018 // statepoint and record them in "Info" structure. Note that similar to 2019 // relocated values we don't do any user adjustments here. 2020 static void rematerializeLiveValues(CallBase *Call, 2021 PartiallyConstructedSafepointRecord &Info, 2022 TargetTransformInfo &TTI) { 2023 const unsigned int ChainLengthThreshold = 10; 2024 2025 // Record values we are going to delete from this statepoint live set. 2026 // We can not di this in following loop due to iterator invalidation. 2027 SmallVector<Value *, 32> LiveValuesToBeDeleted; 2028 2029 for (Value *LiveValue: Info.LiveSet) { 2030 // For each live pointer find its defining chain 2031 SmallVector<Instruction *, 3> ChainToBase; 2032 assert(Info.PointerToBase.count(LiveValue)); 2033 Value *RootOfChain = 2034 findRematerializableChainToBasePointer(ChainToBase, 2035 LiveValue); 2036 2037 // Nothing to do, or chain is too long 2038 if ( ChainToBase.size() == 0 || 2039 ChainToBase.size() > ChainLengthThreshold) 2040 continue; 2041 2042 // Handle the scenario where the RootOfChain is not equal to the 2043 // Base Value, but they are essentially the same phi values. 2044 if (RootOfChain != Info.PointerToBase[LiveValue]) { 2045 PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain); 2046 PHINode *AlternateRootPhi = dyn_cast<PHINode>(Info.PointerToBase[LiveValue]); 2047 if (!OrigRootPhi || !AlternateRootPhi) 2048 continue; 2049 // PHI nodes that have the same incoming values, and belonging to the same 2050 // basic blocks are essentially the same SSA value. When the original phi 2051 // has incoming values with different base pointers, the original phi is 2052 // marked as conflict, and an additional `AlternateRootPhi` with the same 2053 // incoming values get generated by the findBasePointer function. We need 2054 // to identify the newly generated AlternateRootPhi (.base version of phi) 2055 // and RootOfChain (the original phi node itself) are the same, so that we 2056 // can rematerialize the gep and casts. This is a workaround for the 2057 // deficiency in the findBasePointer algorithm. 2058 if (!AreEquivalentPhiNodes(*OrigRootPhi, *AlternateRootPhi)) 2059 continue; 2060 // Now that the phi nodes are proved to be the same, assert that 2061 // findBasePointer's newly generated AlternateRootPhi is present in the 2062 // liveset of the call. 2063 assert(Info.LiveSet.count(AlternateRootPhi)); 2064 } 2065 // Compute cost of this chain 2066 unsigned Cost = chainToBasePointerCost(ChainToBase, TTI); 2067 // TODO: We can also account for cases when we will be able to remove some 2068 // of the rematerialized values by later optimization passes. I.e if 2069 // we rematerialized several intersecting chains. Or if original values 2070 // don't have any uses besides this statepoint. 2071 2072 // For invokes we need to rematerialize each chain twice - for normal and 2073 // for unwind basic blocks. Model this by multiplying cost by two. 2074 if (isa<InvokeInst>(Call)) { 2075 Cost *= 2; 2076 } 2077 // If it's too expensive - skip it 2078 if (Cost >= RematerializationThreshold) 2079 continue; 2080 2081 // Remove value from the live set 2082 LiveValuesToBeDeleted.push_back(LiveValue); 2083 2084 // Clone instructions and record them inside "Info" structure 2085 2086 // Walk backwards to visit top-most instructions first 2087 std::reverse(ChainToBase.begin(), ChainToBase.end()); 2088 2089 // Utility function which clones all instructions from "ChainToBase" 2090 // and inserts them before "InsertBefore". Returns rematerialized value 2091 // which should be used after statepoint. 2092 auto rematerializeChain = [&ChainToBase]( 2093 Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase) { 2094 Instruction *LastClonedValue = nullptr; 2095 Instruction *LastValue = nullptr; 2096 for (Instruction *Instr: ChainToBase) { 2097 // Only GEP's and casts are supported as we need to be careful to not 2098 // introduce any new uses of pointers not in the liveset. 2099 // Note that it's fine to introduce new uses of pointers which were 2100 // otherwise not used after this statepoint. 2101 assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr)); 2102 2103 Instruction *ClonedValue = Instr->clone(); 2104 ClonedValue->insertBefore(InsertBefore); 2105 ClonedValue->setName(Instr->getName() + ".remat"); 2106 2107 // If it is not first instruction in the chain then it uses previously 2108 // cloned value. We should update it to use cloned value. 2109 if (LastClonedValue) { 2110 assert(LastValue); 2111 ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue); 2112 #ifndef NDEBUG 2113 for (auto OpValue : ClonedValue->operand_values()) { 2114 // Assert that cloned instruction does not use any instructions from 2115 // this chain other than LastClonedValue 2116 assert(!is_contained(ChainToBase, OpValue) && 2117 "incorrect use in rematerialization chain"); 2118 // Assert that the cloned instruction does not use the RootOfChain 2119 // or the AlternateLiveBase. 2120 assert(OpValue != RootOfChain && OpValue != AlternateLiveBase); 2121 } 2122 #endif 2123 } else { 2124 // For the first instruction, replace the use of unrelocated base i.e. 2125 // RootOfChain/OrigRootPhi, with the corresponding PHI present in the 2126 // live set. They have been proved to be the same PHI nodes. Note 2127 // that the *only* use of the RootOfChain in the ChainToBase list is 2128 // the first Value in the list. 2129 if (RootOfChain != AlternateLiveBase) 2130 ClonedValue->replaceUsesOfWith(RootOfChain, AlternateLiveBase); 2131 } 2132 2133 LastClonedValue = ClonedValue; 2134 LastValue = Instr; 2135 } 2136 assert(LastClonedValue); 2137 return LastClonedValue; 2138 }; 2139 2140 // Different cases for calls and invokes. For invokes we need to clone 2141 // instructions both on normal and unwind path. 2142 if (isa<CallInst>(Call)) { 2143 Instruction *InsertBefore = Call->getNextNode(); 2144 assert(InsertBefore); 2145 Instruction *RematerializedValue = rematerializeChain( 2146 InsertBefore, RootOfChain, Info.PointerToBase[LiveValue]); 2147 Info.RematerializedValues[RematerializedValue] = LiveValue; 2148 } else { 2149 auto *Invoke = cast<InvokeInst>(Call); 2150 2151 Instruction *NormalInsertBefore = 2152 &*Invoke->getNormalDest()->getFirstInsertionPt(); 2153 Instruction *UnwindInsertBefore = 2154 &*Invoke->getUnwindDest()->getFirstInsertionPt(); 2155 2156 Instruction *NormalRematerializedValue = rematerializeChain( 2157 NormalInsertBefore, RootOfChain, Info.PointerToBase[LiveValue]); 2158 Instruction *UnwindRematerializedValue = rematerializeChain( 2159 UnwindInsertBefore, RootOfChain, Info.PointerToBase[LiveValue]); 2160 2161 Info.RematerializedValues[NormalRematerializedValue] = LiveValue; 2162 Info.RematerializedValues[UnwindRematerializedValue] = LiveValue; 2163 } 2164 } 2165 2166 // Remove rematerializaed values from the live set 2167 for (auto LiveValue: LiveValuesToBeDeleted) { 2168 Info.LiveSet.remove(LiveValue); 2169 } 2170 } 2171 2172 static bool insertParsePoints(Function &F, DominatorTree &DT, 2173 TargetTransformInfo &TTI, 2174 SmallVectorImpl<CallBase *> &ToUpdate) { 2175 #ifndef NDEBUG 2176 // sanity check the input 2177 std::set<CallBase *> Uniqued; 2178 Uniqued.insert(ToUpdate.begin(), ToUpdate.end()); 2179 assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!"); 2180 2181 for (CallBase *Call : ToUpdate) 2182 assert(Call->getFunction() == &F); 2183 #endif 2184 2185 // When inserting gc.relocates for invokes, we need to be able to insert at 2186 // the top of the successor blocks. See the comment on 2187 // normalForInvokeSafepoint on exactly what is needed. Note that this step 2188 // may restructure the CFG. 2189 for (CallBase *Call : ToUpdate) { 2190 auto *II = dyn_cast<InvokeInst>(Call); 2191 if (!II) 2192 continue; 2193 normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT); 2194 normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT); 2195 } 2196 2197 // A list of dummy calls added to the IR to keep various values obviously 2198 // live in the IR. We'll remove all of these when done. 2199 SmallVector<CallInst *, 64> Holders; 2200 2201 // Insert a dummy call with all of the deopt operands we'll need for the 2202 // actual safepoint insertion as arguments. This ensures reference operands 2203 // in the deopt argument list are considered live through the safepoint (and 2204 // thus makes sure they get relocated.) 2205 for (CallBase *Call : ToUpdate) { 2206 SmallVector<Value *, 64> DeoptValues; 2207 2208 for (Value *Arg : GetDeoptBundleOperands(Call)) { 2209 assert(!isUnhandledGCPointerType(Arg->getType()) && 2210 "support for FCA unimplemented"); 2211 if (isHandledGCPointerType(Arg->getType())) 2212 DeoptValues.push_back(Arg); 2213 } 2214 2215 insertUseHolderAfter(Call, DeoptValues, Holders); 2216 } 2217 2218 SmallVector<PartiallyConstructedSafepointRecord, 64> Records(ToUpdate.size()); 2219 2220 // A) Identify all gc pointers which are statically live at the given call 2221 // site. 2222 findLiveReferences(F, DT, ToUpdate, Records); 2223 2224 // B) Find the base pointers for each live pointer 2225 /* scope for caching */ { 2226 // Cache the 'defining value' relation used in the computation and 2227 // insertion of base phis and selects. This ensures that we don't insert 2228 // large numbers of duplicate base_phis. 2229 DefiningValueMapTy DVCache; 2230 2231 for (size_t i = 0; i < Records.size(); i++) { 2232 PartiallyConstructedSafepointRecord &info = Records[i]; 2233 findBasePointers(DT, DVCache, ToUpdate[i], info); 2234 } 2235 } // end of cache scope 2236 2237 // The base phi insertion logic (for any safepoint) may have inserted new 2238 // instructions which are now live at some safepoint. The simplest such 2239 // example is: 2240 // loop: 2241 // phi a <-- will be a new base_phi here 2242 // safepoint 1 <-- that needs to be live here 2243 // gep a + 1 2244 // safepoint 2 2245 // br loop 2246 // We insert some dummy calls after each safepoint to definitely hold live 2247 // the base pointers which were identified for that safepoint. We'll then 2248 // ask liveness for _every_ base inserted to see what is now live. Then we 2249 // remove the dummy calls. 2250 Holders.reserve(Holders.size() + Records.size()); 2251 for (size_t i = 0; i < Records.size(); i++) { 2252 PartiallyConstructedSafepointRecord &Info = Records[i]; 2253 2254 SmallVector<Value *, 128> Bases; 2255 for (auto Pair : Info.PointerToBase) 2256 Bases.push_back(Pair.second); 2257 2258 insertUseHolderAfter(ToUpdate[i], Bases, Holders); 2259 } 2260 2261 // By selecting base pointers, we've effectively inserted new uses. Thus, we 2262 // need to rerun liveness. We may *also* have inserted new defs, but that's 2263 // not the key issue. 2264 recomputeLiveInValues(F, DT, ToUpdate, Records); 2265 2266 if (PrintBasePointers) { 2267 for (auto &Info : Records) { 2268 errs() << "Base Pairs: (w/Relocation)\n"; 2269 for (auto Pair : Info.PointerToBase) { 2270 errs() << " derived "; 2271 Pair.first->printAsOperand(errs(), false); 2272 errs() << " base "; 2273 Pair.second->printAsOperand(errs(), false); 2274 errs() << "\n"; 2275 } 2276 } 2277 } 2278 2279 // It is possible that non-constant live variables have a constant base. For 2280 // example, a GEP with a variable offset from a global. In this case we can 2281 // remove it from the liveset. We already don't add constants to the liveset 2282 // because we assume they won't move at runtime and the GC doesn't need to be 2283 // informed about them. The same reasoning applies if the base is constant. 2284 // Note that the relocation placement code relies on this filtering for 2285 // correctness as it expects the base to be in the liveset, which isn't true 2286 // if the base is constant. 2287 for (auto &Info : Records) 2288 for (auto &BasePair : Info.PointerToBase) 2289 if (isa<Constant>(BasePair.second)) 2290 Info.LiveSet.remove(BasePair.first); 2291 2292 for (CallInst *CI : Holders) 2293 CI->eraseFromParent(); 2294 2295 Holders.clear(); 2296 2297 // In order to reduce live set of statepoint we might choose to rematerialize 2298 // some values instead of relocating them. This is purely an optimization and 2299 // does not influence correctness. 2300 for (size_t i = 0; i < Records.size(); i++) 2301 rematerializeLiveValues(ToUpdate[i], Records[i], TTI); 2302 2303 // We need this to safely RAUW and delete call or invoke return values that 2304 // may themselves be live over a statepoint. For details, please see usage in 2305 // makeStatepointExplicitImpl. 2306 std::vector<DeferredReplacement> Replacements; 2307 2308 // Now run through and replace the existing statepoints with new ones with 2309 // the live variables listed. We do not yet update uses of the values being 2310 // relocated. We have references to live variables that need to 2311 // survive to the last iteration of this loop. (By construction, the 2312 // previous statepoint can not be a live variable, thus we can and remove 2313 // the old statepoint calls as we go.) 2314 for (size_t i = 0; i < Records.size(); i++) 2315 makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements); 2316 2317 ToUpdate.clear(); // prevent accident use of invalid calls. 2318 2319 for (auto &PR : Replacements) 2320 PR.doReplacement(); 2321 2322 Replacements.clear(); 2323 2324 for (auto &Info : Records) { 2325 // These live sets may contain state Value pointers, since we replaced calls 2326 // with operand bundles with calls wrapped in gc.statepoint, and some of 2327 // those calls may have been def'ing live gc pointers. Clear these out to 2328 // avoid accidentally using them. 2329 // 2330 // TODO: We should create a separate data structure that does not contain 2331 // these live sets, and migrate to using that data structure from this point 2332 // onward. 2333 Info.LiveSet.clear(); 2334 Info.PointerToBase.clear(); 2335 } 2336 2337 // Do all the fixups of the original live variables to their relocated selves 2338 SmallVector<Value *, 128> Live; 2339 for (size_t i = 0; i < Records.size(); i++) { 2340 PartiallyConstructedSafepointRecord &Info = Records[i]; 2341 2342 // We can't simply save the live set from the original insertion. One of 2343 // the live values might be the result of a call which needs a safepoint. 2344 // That Value* no longer exists and we need to use the new gc_result. 2345 // Thankfully, the live set is embedded in the statepoint (and updated), so 2346 // we just grab that. 2347 Statepoint Statepoint(Info.StatepointToken); 2348 Live.insert(Live.end(), Statepoint.gc_args_begin(), 2349 Statepoint.gc_args_end()); 2350 #ifndef NDEBUG 2351 // Do some basic sanity checks on our liveness results before performing 2352 // relocation. Relocation can and will turn mistakes in liveness results 2353 // into non-sensical code which is must harder to debug. 2354 // TODO: It would be nice to test consistency as well 2355 assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) && 2356 "statepoint must be reachable or liveness is meaningless"); 2357 for (Value *V : Statepoint.gc_args()) { 2358 if (!isa<Instruction>(V)) 2359 // Non-instruction values trivial dominate all possible uses 2360 continue; 2361 auto *LiveInst = cast<Instruction>(V); 2362 assert(DT.isReachableFromEntry(LiveInst->getParent()) && 2363 "unreachable values should never be live"); 2364 assert(DT.dominates(LiveInst, Info.StatepointToken) && 2365 "basic SSA liveness expectation violated by liveness analysis"); 2366 } 2367 #endif 2368 } 2369 unique_unsorted(Live); 2370 2371 #ifndef NDEBUG 2372 // sanity check 2373 for (auto *Ptr : Live) 2374 assert(isHandledGCPointerType(Ptr->getType()) && 2375 "must be a gc pointer type"); 2376 #endif 2377 2378 relocationViaAlloca(F, DT, Live, Records); 2379 return !Records.empty(); 2380 } 2381 2382 // Handles both return values and arguments for Functions and calls. 2383 template <typename AttrHolder> 2384 static void RemoveNonValidAttrAtIndex(LLVMContext &Ctx, AttrHolder &AH, 2385 unsigned Index) { 2386 AttrBuilder R; 2387 if (AH.getDereferenceableBytes(Index)) 2388 R.addAttribute(Attribute::get(Ctx, Attribute::Dereferenceable, 2389 AH.getDereferenceableBytes(Index))); 2390 if (AH.getDereferenceableOrNullBytes(Index)) 2391 R.addAttribute(Attribute::get(Ctx, Attribute::DereferenceableOrNull, 2392 AH.getDereferenceableOrNullBytes(Index))); 2393 if (AH.getAttributes().hasAttribute(Index, Attribute::NoAlias)) 2394 R.addAttribute(Attribute::NoAlias); 2395 2396 if (!R.empty()) 2397 AH.setAttributes(AH.getAttributes().removeAttributes(Ctx, Index, R)); 2398 } 2399 2400 static void stripNonValidAttributesFromPrototype(Function &F) { 2401 LLVMContext &Ctx = F.getContext(); 2402 2403 for (Argument &A : F.args()) 2404 if (isa<PointerType>(A.getType())) 2405 RemoveNonValidAttrAtIndex(Ctx, F, 2406 A.getArgNo() + AttributeList::FirstArgIndex); 2407 2408 if (isa<PointerType>(F.getReturnType())) 2409 RemoveNonValidAttrAtIndex(Ctx, F, AttributeList::ReturnIndex); 2410 } 2411 2412 /// Certain metadata on instructions are invalid after running RS4GC. 2413 /// Optimizations that run after RS4GC can incorrectly use this metadata to 2414 /// optimize functions. We drop such metadata on the instruction. 2415 static void stripInvalidMetadataFromInstruction(Instruction &I) { 2416 if (!isa<LoadInst>(I) && !isa<StoreInst>(I)) 2417 return; 2418 // These are the attributes that are still valid on loads and stores after 2419 // RS4GC. 2420 // The metadata implying dereferenceability and noalias are (conservatively) 2421 // dropped. This is because semantically, after RewriteStatepointsForGC runs, 2422 // all calls to gc.statepoint "free" the entire heap. Also, gc.statepoint can 2423 // touch the entire heap including noalias objects. Note: The reasoning is 2424 // same as stripping the dereferenceability and noalias attributes that are 2425 // analogous to the metadata counterparts. 2426 // We also drop the invariant.load metadata on the load because that metadata 2427 // implies the address operand to the load points to memory that is never 2428 // changed once it became dereferenceable. This is no longer true after RS4GC. 2429 // Similar reasoning applies to invariant.group metadata, which applies to 2430 // loads within a group. 2431 unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa, 2432 LLVMContext::MD_range, 2433 LLVMContext::MD_alias_scope, 2434 LLVMContext::MD_nontemporal, 2435 LLVMContext::MD_nonnull, 2436 LLVMContext::MD_align, 2437 LLVMContext::MD_type}; 2438 2439 // Drops all metadata on the instruction other than ValidMetadataAfterRS4GC. 2440 I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC); 2441 } 2442 2443 static void stripNonValidDataFromBody(Function &F) { 2444 if (F.empty()) 2445 return; 2446 2447 LLVMContext &Ctx = F.getContext(); 2448 MDBuilder Builder(Ctx); 2449 2450 // Set of invariantstart instructions that we need to remove. 2451 // Use this to avoid invalidating the instruction iterator. 2452 SmallVector<IntrinsicInst*, 12> InvariantStartInstructions; 2453 2454 for (Instruction &I : instructions(F)) { 2455 // invariant.start on memory location implies that the referenced memory 2456 // location is constant and unchanging. This is no longer true after 2457 // RewriteStatepointsForGC runs because there can be calls to gc.statepoint 2458 // which frees the entire heap and the presence of invariant.start allows 2459 // the optimizer to sink the load of a memory location past a statepoint, 2460 // which is incorrect. 2461 if (auto *II = dyn_cast<IntrinsicInst>(&I)) 2462 if (II->getIntrinsicID() == Intrinsic::invariant_start) { 2463 InvariantStartInstructions.push_back(II); 2464 continue; 2465 } 2466 2467 if (MDNode *Tag = I.getMetadata(LLVMContext::MD_tbaa)) { 2468 MDNode *MutableTBAA = Builder.createMutableTBAAAccessTag(Tag); 2469 I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA); 2470 } 2471 2472 stripInvalidMetadataFromInstruction(I); 2473 2474 if (auto *Call = dyn_cast<CallBase>(&I)) { 2475 for (int i = 0, e = Call->arg_size(); i != e; i++) 2476 if (isa<PointerType>(Call->getArgOperand(i)->getType())) 2477 RemoveNonValidAttrAtIndex(Ctx, *Call, 2478 i + AttributeList::FirstArgIndex); 2479 if (isa<PointerType>(Call->getType())) 2480 RemoveNonValidAttrAtIndex(Ctx, *Call, AttributeList::ReturnIndex); 2481 } 2482 } 2483 2484 // Delete the invariant.start instructions and RAUW undef. 2485 for (auto *II : InvariantStartInstructions) { 2486 II->replaceAllUsesWith(UndefValue::get(II->getType())); 2487 II->eraseFromParent(); 2488 } 2489 } 2490 2491 /// Returns true if this function should be rewritten by this pass. The main 2492 /// point of this function is as an extension point for custom logic. 2493 static bool shouldRewriteStatepointsIn(Function &F) { 2494 // TODO: This should check the GCStrategy 2495 if (F.hasGC()) { 2496 const auto &FunctionGCName = F.getGC(); 2497 const StringRef StatepointExampleName("statepoint-example"); 2498 const StringRef CoreCLRName("coreclr"); 2499 return (StatepointExampleName == FunctionGCName) || 2500 (CoreCLRName == FunctionGCName); 2501 } else 2502 return false; 2503 } 2504 2505 static void stripNonValidData(Module &M) { 2506 #ifndef NDEBUG 2507 assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!"); 2508 #endif 2509 2510 for (Function &F : M) 2511 stripNonValidAttributesFromPrototype(F); 2512 2513 for (Function &F : M) 2514 stripNonValidDataFromBody(F); 2515 } 2516 2517 bool RewriteStatepointsForGC::runOnFunction(Function &F, DominatorTree &DT, 2518 TargetTransformInfo &TTI, 2519 const TargetLibraryInfo &TLI) { 2520 assert(!F.isDeclaration() && !F.empty() && 2521 "need function body to rewrite statepoints in"); 2522 assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision"); 2523 2524 auto NeedsRewrite = [&TLI](Instruction &I) { 2525 if (const auto *Call = dyn_cast<CallBase>(&I)) 2526 return !callsGCLeafFunction(Call, TLI) && !isStatepoint(Call); 2527 return false; 2528 }; 2529 2530 // Delete any unreachable statepoints so that we don't have unrewritten 2531 // statepoints surviving this pass. This makes testing easier and the 2532 // resulting IR less confusing to human readers. 2533 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); 2534 bool MadeChange = removeUnreachableBlocks(F, &DTU); 2535 // Flush the Dominator Tree. 2536 DTU.getDomTree(); 2537 2538 // Gather all the statepoints which need rewritten. Be careful to only 2539 // consider those in reachable code since we need to ask dominance queries 2540 // when rewriting. We'll delete the unreachable ones in a moment. 2541 SmallVector<CallBase *, 64> ParsePointNeeded; 2542 for (Instruction &I : instructions(F)) { 2543 // TODO: only the ones with the flag set! 2544 if (NeedsRewrite(I)) { 2545 // NOTE removeUnreachableBlocks() is stronger than 2546 // DominatorTree::isReachableFromEntry(). In other words 2547 // removeUnreachableBlocks can remove some blocks for which 2548 // isReachableFromEntry() returns true. 2549 assert(DT.isReachableFromEntry(I.getParent()) && 2550 "no unreachable blocks expected"); 2551 ParsePointNeeded.push_back(cast<CallBase>(&I)); 2552 } 2553 } 2554 2555 // Return early if no work to do. 2556 if (ParsePointNeeded.empty()) 2557 return MadeChange; 2558 2559 // As a prepass, go ahead and aggressively destroy single entry phi nodes. 2560 // These are created by LCSSA. They have the effect of increasing the size 2561 // of liveness sets for no good reason. It may be harder to do this post 2562 // insertion since relocations and base phis can confuse things. 2563 for (BasicBlock &BB : F) 2564 if (BB.getUniquePredecessor()) { 2565 MadeChange = true; 2566 FoldSingleEntryPHINodes(&BB); 2567 } 2568 2569 // Before we start introducing relocations, we want to tweak the IR a bit to 2570 // avoid unfortunate code generation effects. The main example is that we 2571 // want to try to make sure the comparison feeding a branch is after any 2572 // safepoints. Otherwise, we end up with a comparison of pre-relocation 2573 // values feeding a branch after relocation. This is semantically correct, 2574 // but results in extra register pressure since both the pre-relocation and 2575 // post-relocation copies must be available in registers. For code without 2576 // relocations this is handled elsewhere, but teaching the scheduler to 2577 // reverse the transform we're about to do would be slightly complex. 2578 // Note: This may extend the live range of the inputs to the icmp and thus 2579 // increase the liveset of any statepoint we move over. This is profitable 2580 // as long as all statepoints are in rare blocks. If we had in-register 2581 // lowering for live values this would be a much safer transform. 2582 auto getConditionInst = [](Instruction *TI) -> Instruction * { 2583 if (auto *BI = dyn_cast<BranchInst>(TI)) 2584 if (BI->isConditional()) 2585 return dyn_cast<Instruction>(BI->getCondition()); 2586 // TODO: Extend this to handle switches 2587 return nullptr; 2588 }; 2589 for (BasicBlock &BB : F) { 2590 Instruction *TI = BB.getTerminator(); 2591 if (auto *Cond = getConditionInst(TI)) 2592 // TODO: Handle more than just ICmps here. We should be able to move 2593 // most instructions without side effects or memory access. 2594 if (isa<ICmpInst>(Cond) && Cond->hasOneUse()) { 2595 MadeChange = true; 2596 Cond->moveBefore(TI); 2597 } 2598 } 2599 2600 // Nasty workaround - The base computation code in the main algorithm doesn't 2601 // consider the fact that a GEP can be used to convert a scalar to a vector. 2602 // The right fix for this is to integrate GEPs into the base rewriting 2603 // algorithm properly, this is just a short term workaround to prevent 2604 // crashes by canonicalizing such GEPs into fully vector GEPs. 2605 for (Instruction &I : instructions(F)) { 2606 if (!isa<GetElementPtrInst>(I)) 2607 continue; 2608 2609 unsigned VF = 0; 2610 for (unsigned i = 0; i < I.getNumOperands(); i++) 2611 if (I.getOperand(i)->getType()->isVectorTy()) { 2612 assert(VF == 0 || 2613 VF == I.getOperand(i)->getType()->getVectorNumElements()); 2614 VF = I.getOperand(i)->getType()->getVectorNumElements(); 2615 } 2616 2617 // It's the vector to scalar traversal through the pointer operand which 2618 // confuses base pointer rewriting, so limit ourselves to that case. 2619 if (!I.getOperand(0)->getType()->isVectorTy() && VF != 0) { 2620 IRBuilder<> B(&I); 2621 auto *Splat = B.CreateVectorSplat(VF, I.getOperand(0)); 2622 I.setOperand(0, Splat); 2623 MadeChange = true; 2624 } 2625 } 2626 2627 MadeChange |= insertParsePoints(F, DT, TTI, ParsePointNeeded); 2628 return MadeChange; 2629 } 2630 2631 // liveness computation via standard dataflow 2632 // ------------------------------------------------------------------- 2633 2634 // TODO: Consider using bitvectors for liveness, the set of potentially 2635 // interesting values should be small and easy to pre-compute. 2636 2637 /// Compute the live-in set for the location rbegin starting from 2638 /// the live-out set of the basic block 2639 static void computeLiveInValues(BasicBlock::reverse_iterator Begin, 2640 BasicBlock::reverse_iterator End, 2641 SetVector<Value *> &LiveTmp) { 2642 for (auto &I : make_range(Begin, End)) { 2643 // KILL/Def - Remove this definition from LiveIn 2644 LiveTmp.remove(&I); 2645 2646 // Don't consider *uses* in PHI nodes, we handle their contribution to 2647 // predecessor blocks when we seed the LiveOut sets 2648 if (isa<PHINode>(I)) 2649 continue; 2650 2651 // USE - Add to the LiveIn set for this instruction 2652 for (Value *V : I.operands()) { 2653 assert(!isUnhandledGCPointerType(V->getType()) && 2654 "support for FCA unimplemented"); 2655 if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) { 2656 // The choice to exclude all things constant here is slightly subtle. 2657 // There are two independent reasons: 2658 // - We assume that things which are constant (from LLVM's definition) 2659 // do not move at runtime. For example, the address of a global 2660 // variable is fixed, even though it's contents may not be. 2661 // - Second, we can't disallow arbitrary inttoptr constants even 2662 // if the language frontend does. Optimization passes are free to 2663 // locally exploit facts without respect to global reachability. This 2664 // can create sections of code which are dynamically unreachable and 2665 // contain just about anything. (see constants.ll in tests) 2666 LiveTmp.insert(V); 2667 } 2668 } 2669 } 2670 } 2671 2672 static void computeLiveOutSeed(BasicBlock *BB, SetVector<Value *> &LiveTmp) { 2673 for (BasicBlock *Succ : successors(BB)) { 2674 for (auto &I : *Succ) { 2675 PHINode *PN = dyn_cast<PHINode>(&I); 2676 if (!PN) 2677 break; 2678 2679 Value *V = PN->getIncomingValueForBlock(BB); 2680 assert(!isUnhandledGCPointerType(V->getType()) && 2681 "support for FCA unimplemented"); 2682 if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) 2683 LiveTmp.insert(V); 2684 } 2685 } 2686 } 2687 2688 static SetVector<Value *> computeKillSet(BasicBlock *BB) { 2689 SetVector<Value *> KillSet; 2690 for (Instruction &I : *BB) 2691 if (isHandledGCPointerType(I.getType())) 2692 KillSet.insert(&I); 2693 return KillSet; 2694 } 2695 2696 #ifndef NDEBUG 2697 /// Check that the items in 'Live' dominate 'TI'. This is used as a basic 2698 /// sanity check for the liveness computation. 2699 static void checkBasicSSA(DominatorTree &DT, SetVector<Value *> &Live, 2700 Instruction *TI, bool TermOkay = false) { 2701 for (Value *V : Live) { 2702 if (auto *I = dyn_cast<Instruction>(V)) { 2703 // The terminator can be a member of the LiveOut set. LLVM's definition 2704 // of instruction dominance states that V does not dominate itself. As 2705 // such, we need to special case this to allow it. 2706 if (TermOkay && TI == I) 2707 continue; 2708 assert(DT.dominates(I, TI) && 2709 "basic SSA liveness expectation violated by liveness analysis"); 2710 } 2711 } 2712 } 2713 2714 /// Check that all the liveness sets used during the computation of liveness 2715 /// obey basic SSA properties. This is useful for finding cases where we miss 2716 /// a def. 2717 static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data, 2718 BasicBlock &BB) { 2719 checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator()); 2720 checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true); 2721 checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator()); 2722 } 2723 #endif 2724 2725 static void computeLiveInValues(DominatorTree &DT, Function &F, 2726 GCPtrLivenessData &Data) { 2727 SmallSetVector<BasicBlock *, 32> Worklist; 2728 2729 // Seed the liveness for each individual block 2730 for (BasicBlock &BB : F) { 2731 Data.KillSet[&BB] = computeKillSet(&BB); 2732 Data.LiveSet[&BB].clear(); 2733 computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB]); 2734 2735 #ifndef NDEBUG 2736 for (Value *Kill : Data.KillSet[&BB]) 2737 assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill"); 2738 #endif 2739 2740 Data.LiveOut[&BB] = SetVector<Value *>(); 2741 computeLiveOutSeed(&BB, Data.LiveOut[&BB]); 2742 Data.LiveIn[&BB] = Data.LiveSet[&BB]; 2743 Data.LiveIn[&BB].set_union(Data.LiveOut[&BB]); 2744 Data.LiveIn[&BB].set_subtract(Data.KillSet[&BB]); 2745 if (!Data.LiveIn[&BB].empty()) 2746 Worklist.insert(pred_begin(&BB), pred_end(&BB)); 2747 } 2748 2749 // Propagate that liveness until stable 2750 while (!Worklist.empty()) { 2751 BasicBlock *BB = Worklist.pop_back_val(); 2752 2753 // Compute our new liveout set, then exit early if it hasn't changed despite 2754 // the contribution of our successor. 2755 SetVector<Value *> LiveOut = Data.LiveOut[BB]; 2756 const auto OldLiveOutSize = LiveOut.size(); 2757 for (BasicBlock *Succ : successors(BB)) { 2758 assert(Data.LiveIn.count(Succ)); 2759 LiveOut.set_union(Data.LiveIn[Succ]); 2760 } 2761 // assert OutLiveOut is a subset of LiveOut 2762 if (OldLiveOutSize == LiveOut.size()) { 2763 // If the sets are the same size, then we didn't actually add anything 2764 // when unioning our successors LiveIn. Thus, the LiveIn of this block 2765 // hasn't changed. 2766 continue; 2767 } 2768 Data.LiveOut[BB] = LiveOut; 2769 2770 // Apply the effects of this basic block 2771 SetVector<Value *> LiveTmp = LiveOut; 2772 LiveTmp.set_union(Data.LiveSet[BB]); 2773 LiveTmp.set_subtract(Data.KillSet[BB]); 2774 2775 assert(Data.LiveIn.count(BB)); 2776 const SetVector<Value *> &OldLiveIn = Data.LiveIn[BB]; 2777 // assert: OldLiveIn is a subset of LiveTmp 2778 if (OldLiveIn.size() != LiveTmp.size()) { 2779 Data.LiveIn[BB] = LiveTmp; 2780 Worklist.insert(pred_begin(BB), pred_end(BB)); 2781 } 2782 } // while (!Worklist.empty()) 2783 2784 #ifndef NDEBUG 2785 // Sanity check our output against SSA properties. This helps catch any 2786 // missing kills during the above iteration. 2787 for (BasicBlock &BB : F) 2788 checkBasicSSA(DT, Data, BB); 2789 #endif 2790 } 2791 2792 static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data, 2793 StatepointLiveSetTy &Out) { 2794 BasicBlock *BB = Inst->getParent(); 2795 2796 // Note: The copy is intentional and required 2797 assert(Data.LiveOut.count(BB)); 2798 SetVector<Value *> LiveOut = Data.LiveOut[BB]; 2799 2800 // We want to handle the statepoint itself oddly. It's 2801 // call result is not live (normal), nor are it's arguments 2802 // (unless they're used again later). This adjustment is 2803 // specifically what we need to relocate 2804 computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(), 2805 LiveOut); 2806 LiveOut.remove(Inst); 2807 Out.insert(LiveOut.begin(), LiveOut.end()); 2808 } 2809 2810 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, 2811 CallBase *Call, 2812 PartiallyConstructedSafepointRecord &Info) { 2813 StatepointLiveSetTy Updated; 2814 findLiveSetAtInst(Call, RevisedLivenessData, Updated); 2815 2816 // We may have base pointers which are now live that weren't before. We need 2817 // to update the PointerToBase structure to reflect this. 2818 for (auto V : Updated) 2819 if (Info.PointerToBase.insert({V, V}).second) { 2820 assert(isKnownBaseResult(V) && 2821 "Can't find base for unexpected live value!"); 2822 continue; 2823 } 2824 2825 #ifndef NDEBUG 2826 for (auto V : Updated) 2827 assert(Info.PointerToBase.count(V) && 2828 "Must be able to find base for live value!"); 2829 #endif 2830 2831 // Remove any stale base mappings - this can happen since our liveness is 2832 // more precise then the one inherent in the base pointer analysis. 2833 DenseSet<Value *> ToErase; 2834 for (auto KVPair : Info.PointerToBase) 2835 if (!Updated.count(KVPair.first)) 2836 ToErase.insert(KVPair.first); 2837 2838 for (auto *V : ToErase) 2839 Info.PointerToBase.erase(V); 2840 2841 #ifndef NDEBUG 2842 for (auto KVPair : Info.PointerToBase) 2843 assert(Updated.count(KVPair.first) && "record for non-live value"); 2844 #endif 2845 2846 Info.LiveSet = Updated; 2847 } 2848