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