brintos / llvm-project-archived public Read only

1//===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Rewrite call/invoke instructions so as to make potential relocations10// performed by the garbage collector explicit in the IR.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Transforms/Scalar/RewriteStatepointsForGC.h"15 16#include "llvm/ADT/ArrayRef.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/DenseSet.h"19#include "llvm/ADT/MapVector.h"20#include "llvm/ADT/STLExtras.h"21#include "llvm/ADT/Sequence.h"22#include "llvm/ADT/SetVector.h"23#include "llvm/ADT/SmallVector.h"24#include "llvm/ADT/StringRef.h"25#include "llvm/ADT/iterator_range.h"26#include "llvm/Analysis/DomTreeUpdater.h"27#include "llvm/Analysis/TargetLibraryInfo.h"28#include "llvm/Analysis/TargetTransformInfo.h"29#include "llvm/IR/Argument.h"30#include "llvm/IR/AttributeMask.h"31#include "llvm/IR/Attributes.h"32#include "llvm/IR/BasicBlock.h"33#include "llvm/IR/CallingConv.h"34#include "llvm/IR/Constant.h"35#include "llvm/IR/Constants.h"36#include "llvm/IR/DataLayout.h"37#include "llvm/IR/DerivedTypes.h"38#include "llvm/IR/Dominators.h"39#include "llvm/IR/Function.h"40#include "llvm/IR/GCStrategy.h"41#include "llvm/IR/IRBuilder.h"42#include "llvm/IR/InstIterator.h"43#include "llvm/IR/InstrTypes.h"44#include "llvm/IR/Instruction.h"45#include "llvm/IR/Instructions.h"46#include "llvm/IR/IntrinsicInst.h"47#include "llvm/IR/Intrinsics.h"48#include "llvm/IR/LLVMContext.h"49#include "llvm/IR/MDBuilder.h"50#include "llvm/IR/Metadata.h"51#include "llvm/IR/Module.h"52#include "llvm/IR/Statepoint.h"53#include "llvm/IR/Type.h"54#include "llvm/IR/User.h"55#include "llvm/IR/Value.h"56#include "llvm/IR/ValueHandle.h"57#include "llvm/Support/Casting.h"58#include "llvm/Support/CommandLine.h"59#include "llvm/Support/Compiler.h"60#include "llvm/Support/Debug.h"61#include "llvm/Support/ErrorHandling.h"62#include "llvm/Support/raw_ostream.h"63#include "llvm/Transforms/Utils/BasicBlockUtils.h"64#include "llvm/Transforms/Utils/Local.h"65#include "llvm/Transforms/Utils/PromoteMemToReg.h"66#include <cassert>67#include <cstddef>68#include <cstdint>69#include <iterator>70#include <optional>71#include <set>72#include <string>73#include <utility>74#include <vector>75 76#define DEBUG_TYPE "rewrite-statepoints-for-gc"77 78using namespace llvm;79 80// Print the liveset found at the insert location81static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden,82                                  cl::init(false));83static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden,84                                      cl::init(false));85 86// Print out the base pointers for debugging87static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden,88                                       cl::init(false));89 90// Cost threshold measuring when it is profitable to rematerialize value instead91// of relocating it92static cl::opt<unsigned>93RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden,94                           cl::init(6));95 96#ifdef EXPENSIVE_CHECKS97static bool ClobberNonLive = true;98#else99static bool ClobberNonLive = false;100#endif101 102static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",103                                                  cl::location(ClobberNonLive),104                                                  cl::Hidden);105 106static cl::opt<bool>107    AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",108                                   cl::Hidden, cl::init(true));109 110static cl::opt<bool> RematDerivedAtUses("rs4gc-remat-derived-at-uses",111                                        cl::Hidden, cl::init(true));112 113/// The IR fed into RewriteStatepointsForGC may have had attributes and114/// metadata implying dereferenceability that are no longer valid/correct after115/// RewriteStatepointsForGC has run. This is because semantically, after116/// RewriteStatepointsForGC runs, all calls to gc.statepoint "free" the entire117/// heap. stripNonValidData (conservatively) restores118/// correctness by erasing all attributes in the module that externally imply119/// dereferenceability. Similar reasoning also applies to the noalias120/// attributes and metadata. gc.statepoint can touch the entire heap including121/// noalias objects.122/// Apart from attributes and metadata, we also remove instructions that imply123/// constant physical memory: llvm.invariant.start.124static void stripNonValidData(Module &M);125 126// Find the GC strategy for a function, or null if it doesn't have one.127static std::unique_ptr<GCStrategy> findGCStrategy(Function &F);128 129static bool shouldRewriteStatepointsIn(Function &F);130 131PreservedAnalyses RewriteStatepointsForGC::run(Module &M,132                                               ModuleAnalysisManager &AM) {133  bool Changed = false;134  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();135  for (Function &F : M) {136    // Nothing to do for declarations.137    if (F.isDeclaration() || F.empty())138      continue;139 140    // Policy choice says not to rewrite - the most common reason is that we're141    // compiling code without a GCStrategy.142    if (!shouldRewriteStatepointsIn(F))143      continue;144 145    auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);146    auto &TTI = FAM.getResult<TargetIRAnalysis>(F);147    auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);148    Changed |= runOnFunction(F, DT, TTI, TLI);149  }150  if (!Changed)151    return PreservedAnalyses::all();152 153  // stripNonValidData asserts that shouldRewriteStatepointsIn154  // returns true for at least one function in the module.  Since at least155  // one function changed, we know that the precondition is satisfied.156  stripNonValidData(M);157 158  PreservedAnalyses PA;159  PA.preserve<TargetIRAnalysis>();160  PA.preserve<TargetLibraryAnalysis>();161  return PA;162}163 164namespace {165 166struct GCPtrLivenessData {167  /// Values defined in this block.168  MapVector<BasicBlock *, SetVector<Value *>> KillSet;169 170  /// Values used in this block (and thus live); does not included values171  /// killed within this block.172  MapVector<BasicBlock *, SetVector<Value *>> LiveSet;173 174  /// Values live into this basic block (i.e. used by any175  /// instruction in this basic block or ones reachable from here)176  MapVector<BasicBlock *, SetVector<Value *>> LiveIn;177 178  /// Values live out of this basic block (i.e. live into179  /// any successor block)180  MapVector<BasicBlock *, SetVector<Value *>> LiveOut;181};182 183// The type of the internal cache used inside the findBasePointers family184// of functions.  From the callers perspective, this is an opaque type and185// should not be inspected.186//187// In the actual implementation this caches two relations:188// - The base relation itself (i.e. this pointer is based on that one)189// - The base defining value relation (i.e. before base_phi insertion)190// Generally, after the execution of a full findBasePointer call, only the191// base relation will remain.  Internally, we add a mixture of the two192// types, then update all the second type to the first type193using DefiningValueMapTy = MapVector<Value *, Value *>;194using IsKnownBaseMapTy = MapVector<Value *, bool>;195using PointerToBaseTy = MapVector<Value *, Value *>;196using StatepointLiveSetTy = SetVector<Value *>;197using RematerializedValueMapTy =198    MapVector<AssertingVH<Instruction>, AssertingVH<Value>>;199 200struct PartiallyConstructedSafepointRecord {201  /// The set of values known to be live across this safepoint202  StatepointLiveSetTy LiveSet;203 204  /// The *new* gc.statepoint instruction itself.  This produces the token205  /// that normal path gc.relocates and the gc.result are tied to.206  GCStatepointInst *StatepointToken;207 208  /// Instruction to which exceptional gc relocates are attached209  /// Makes it easier to iterate through them during relocationViaAlloca.210  Instruction *UnwindToken;211 212  /// Record live values we are rematerialized instead of relocating.213  /// They are not included into 'LiveSet' field.214  /// Maps rematerialized copy to it's original value.215  RematerializedValueMapTy RematerializedValues;216};217 218struct RematerizlizationCandidateRecord {219  // Chain from derived pointer to base.220  SmallVector<Instruction *, 3> ChainToBase;221  // Original base.222  Value *RootOfChain;223  // Cost of chain.224  InstructionCost Cost;225};226using RematCandTy = MapVector<Value *, RematerizlizationCandidateRecord>;227 228} // end anonymous namespace229 230static ArrayRef<Use> GetDeoptBundleOperands(const CallBase *Call) {231  std::optional<OperandBundleUse> DeoptBundle =232      Call->getOperandBundle(LLVMContext::OB_deopt);233 234  if (!DeoptBundle) {235    assert(AllowStatepointWithNoDeoptInfo &&236           "Found non-leaf call without deopt info!");237    return {};238  }239 240  return DeoptBundle->Inputs;241}242 243/// Compute the live-in set for every basic block in the function244static void computeLiveInValues(DominatorTree &DT, Function &F,245                                GCPtrLivenessData &Data, GCStrategy *GC);246 247/// Given results from the dataflow liveness computation, find the set of live248/// Values at a particular instruction.249static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,250                              StatepointLiveSetTy &out, GCStrategy *GC);251 252static bool isGCPointerType(Type *T, GCStrategy *GC) {253  assert(GC && "GC Strategy for isGCPointerType cannot be null");254 255  if (!isa<PointerType>(T))256    return false;257 258  // conservative - same as StatepointLowering259  return GC->isGCManagedPointer(T).value_or(true);260}261 262// Return true if this type is one which a) is a gc pointer or contains a GC263// pointer and b) is of a type this code expects to encounter as a live value.264// (The insertion code will assert that a type which matches (a) and not (b)265// is not encountered.)266static bool isHandledGCPointerType(Type *T, GCStrategy *GC) {267  // We fully support gc pointers268  if (isGCPointerType(T, GC))269    return true;270  // We partially support vectors of gc pointers. The code will assert if it271  // can't handle something.272  if (auto VT = dyn_cast<VectorType>(T))273    if (isGCPointerType(VT->getElementType(), GC))274      return true;275  return false;276}277 278#ifndef NDEBUG279/// Returns true if this type contains a gc pointer whether we know how to280/// handle that type or not.281static bool containsGCPtrType(Type *Ty, GCStrategy *GC) {282  if (isGCPointerType(Ty, GC))283    return true;284  if (VectorType *VT = dyn_cast<VectorType>(Ty))285    return isGCPointerType(VT->getScalarType(), GC);286  if (ArrayType *AT = dyn_cast<ArrayType>(Ty))287    return containsGCPtrType(AT->getElementType(), GC);288  if (StructType *ST = dyn_cast<StructType>(Ty))289    return llvm::any_of(ST->elements(),290                        [GC](Type *Ty) { return containsGCPtrType(Ty, GC); });291  return false;292}293 294// Returns true if this is a type which a) is a gc pointer or contains a GC295// pointer and b) is of a type which the code doesn't expect (i.e. first class296// aggregates).  Used to trip assertions.297static bool isUnhandledGCPointerType(Type *Ty, GCStrategy *GC) {298  return containsGCPtrType(Ty, GC) && !isHandledGCPointerType(Ty, GC);299}300#endif301 302// Return the name of the value suffixed with the provided value, or if the303// value didn't have a name, the default value specified.304static std::string suffixed_name_or(Value *V, StringRef Suffix,305                                    StringRef DefaultName) {306  return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str();307}308 309// Conservatively identifies any definitions which might be live at the310// given instruction. The  analysis is performed immediately before the311// given instruction. Values defined by that instruction are not considered312// live.  Values used by that instruction are considered live.313static void analyzeParsePointLiveness(314    DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call,315    PartiallyConstructedSafepointRecord &Result, GCStrategy *GC) {316  StatepointLiveSetTy LiveSet;317  findLiveSetAtInst(Call, OriginalLivenessData, LiveSet, GC);318 319  if (PrintLiveSet) {320    dbgs() << "Live Variables:\n";321    for (Value *V : LiveSet)322      dbgs() << " " << V->getName() << " " << *V << "\n";323  }324  if (PrintLiveSetSize) {325    dbgs() << "Safepoint For: " << Call->getCalledOperand()->getName() << "\n";326    dbgs() << "Number live values: " << LiveSet.size() << "\n";327  }328  Result.LiveSet = LiveSet;329}330 331/// Returns true if V is a known base.332static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases);333 334/// Caches the IsKnownBase flag for a value and asserts that it wasn't present335/// in the cache before.336static void setKnownBase(Value *V, bool IsKnownBase,337                         IsKnownBaseMapTy &KnownBases);338 339static Value *findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache,340                                    IsKnownBaseMapTy &KnownBases);341 342/// Return a base defining value for the 'Index' element of the given vector343/// instruction 'I'.  If Index is null, returns a BDV for the entire vector344/// 'I'.  As an optimization, this method will try to determine when the345/// element is known to already be a base pointer.  If this can be established,346/// the second value in the returned pair will be true.  Note that either a347/// vector or a pointer typed value can be returned.  For the former, the348/// vector returned is a BDV (and possibly a base) of the entire vector 'I'.349/// If the later, the return pointer is a BDV (or possibly a base) for the350/// particular element in 'I'.351static Value *findBaseDefiningValueOfVector(Value *I, DefiningValueMapTy &Cache,352                                            IsKnownBaseMapTy &KnownBases) {353  // Each case parallels findBaseDefiningValue below, see that code for354  // detailed motivation.355 356  auto Cached = Cache.find(I);357  if (Cached != Cache.end())358    return Cached->second;359 360  if (isa<Argument>(I)) {361    // An incoming argument to the function is a base pointer362    Cache[I] = I;363    setKnownBase(I, /* IsKnownBase */true, KnownBases);364    return I;365  }366 367  if (isa<Constant>(I)) {368    // Base of constant vector consists only of constant null pointers.369    // For reasoning see similar case inside 'findBaseDefiningValue' function.370    auto *CAZ = ConstantAggregateZero::get(I->getType());371    Cache[I] = CAZ;372    setKnownBase(CAZ, /* IsKnownBase */true, KnownBases);373    return CAZ;374  }375 376  if (isa<LoadInst>(I)) {377    Cache[I] = I;378    setKnownBase(I, /* IsKnownBase */true, KnownBases);379    return I;380  }381 382  if (isa<InsertElementInst>(I)) {383    // We don't know whether this vector contains entirely base pointers or384    // not.  To be conservatively correct, we treat it as a BDV and will385    // duplicate code as needed to construct a parallel vector of bases.386    Cache[I] = I;387    setKnownBase(I, /* IsKnownBase */false, KnownBases);388    return I;389  }390 391  if (isa<ShuffleVectorInst>(I)) {392    // We don't know whether this vector contains entirely base pointers or393    // not.  To be conservatively correct, we treat it as a BDV and will394    // duplicate code as needed to construct a parallel vector of bases.395    // TODO: There a number of local optimizations which could be applied here396    // for particular sufflevector patterns.397    Cache[I] = I;398    setKnownBase(I, /* IsKnownBase */false, KnownBases);399    return I;400  }401 402  // The behavior of getelementptr instructions is the same for vector and403  // non-vector data types.404  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {405    auto *BDV =406        findBaseDefiningValue(GEP->getPointerOperand(), Cache, KnownBases);407    Cache[GEP] = BDV;408    return BDV;409  }410 411  // The behavior of freeze instructions is the same for vector and412  // non-vector data types.413  if (auto *Freeze = dyn_cast<FreezeInst>(I)) {414    auto *BDV = findBaseDefiningValue(Freeze->getOperand(0), Cache, KnownBases);415    Cache[Freeze] = BDV;416    return BDV;417  }418 419  // If the pointer comes through a bitcast of a vector of pointers to420  // a vector of another type of pointer, then look through the bitcast421  if (auto *BC = dyn_cast<BitCastInst>(I)) {422    auto *BDV = findBaseDefiningValue(BC->getOperand(0), Cache, KnownBases);423    Cache[BC] = BDV;424    return BDV;425  }426 427  // We assume that functions in the source language only return base428  // pointers.  This should probably be generalized via attributes to support429  // both source language and internal functions.430  if (isa<CallInst>(I) || isa<InvokeInst>(I)) {431    Cache[I] = I;432    setKnownBase(I, /* IsKnownBase */true, KnownBases);433    return I;434  }435 436  // A PHI or Select is a base defining value.  The outer findBasePointer437  // algorithm is responsible for constructing a base value for this BDV.438  assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&439         "unknown vector instruction - no base found for vector element");440  Cache[I] = I;441  setKnownBase(I, /* IsKnownBase */false, KnownBases);442  return I;443}444 445/// Helper function for findBasePointer - Will return a value which either a)446/// defines the base pointer for the input, b) blocks the simple search447/// (i.e. a PHI or Select of two derived pointers), or c) involves a change448/// from pointer to vector type or back.449static Value *findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache,450                                    IsKnownBaseMapTy &KnownBases) {451  assert(I->getType()->isPtrOrPtrVectorTy() &&452         "Illegal to ask for the base pointer of a non-pointer type");453  auto Cached = Cache.find(I);454  if (Cached != Cache.end())455    return Cached->second;456 457  if (I->getType()->isVectorTy())458    return findBaseDefiningValueOfVector(I, Cache, KnownBases);459 460  if (isa<Argument>(I)) {461    // An incoming argument to the function is a base pointer462    // We should have never reached here if this argument isn't an gc value463    Cache[I] = I;464    setKnownBase(I, /* IsKnownBase */true, KnownBases);465    return I;466  }467 468  if (isa<Constant>(I)) {469    // We assume that objects with a constant base (e.g. a global) can't move470    // and don't need to be reported to the collector because they are always471    // live. Besides global references, all kinds of constants (e.g. undef,472    // constant expressions, null pointers) can be introduced by the inliner or473    // the optimizer, especially on dynamically dead paths.474    // Here we treat all of them as having single null base. By doing this we475    // trying to avoid problems reporting various conflicts in a form of476    // "phi (const1, const2)" or "phi (const, regular gc ptr)".477    // See constant.ll file for relevant test cases.478 479    auto *CPN = ConstantPointerNull::get(cast<PointerType>(I->getType()));480    Cache[I] = CPN;481    setKnownBase(CPN, /* IsKnownBase */true, KnownBases);482    return CPN;483  }484 485  // inttoptrs in an integral address space are currently ill-defined.  We486  // treat them as defining base pointers here for consistency with the487  // constant rule above and because we don't really have a better semantic488  // to give them.  Note that the optimizer is always free to insert undefined489  // behavior on dynamically dead paths as well.490  if (isa<IntToPtrInst>(I)) {491    Cache[I] = I;492    setKnownBase(I, /* IsKnownBase */true, KnownBases);493    return I;494  }495 496  if (CastInst *CI = dyn_cast<CastInst>(I)) {497    Value *Def = CI->stripPointerCasts();498    // If stripping pointer casts changes the address space there is an499    // addrspacecast in between.500    assert(cast<PointerType>(Def->getType())->getAddressSpace() ==501               cast<PointerType>(CI->getType())->getAddressSpace() &&502           "unsupported addrspacecast");503    // If we find a cast instruction here, it means we've found a cast which is504    // not simply a pointer cast (i.e. an inttoptr).  We don't know how to505    // handle int->ptr conversion.506    assert(!isa<CastInst>(Def) && "shouldn't find another cast here");507    auto *BDV = findBaseDefiningValue(Def, Cache, KnownBases);508    Cache[CI] = BDV;509    return BDV;510  }511 512  if (isa<LoadInst>(I)) {513    // The value loaded is an gc base itself514    Cache[I] = I;515    setKnownBase(I, /* IsKnownBase */true, KnownBases);516    return I;517  }518 519  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {520    // The base of this GEP is the base521    auto *BDV =522        findBaseDefiningValue(GEP->getPointerOperand(), Cache, KnownBases);523    Cache[GEP] = BDV;524    return BDV;525  }526 527  if (auto *Freeze = dyn_cast<FreezeInst>(I)) {528    auto *BDV = findBaseDefiningValue(Freeze->getOperand(0), Cache, KnownBases);529    Cache[Freeze] = BDV;530    return BDV;531  }532 533  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {534    switch (II->getIntrinsicID()) {535    default:536      // fall through to general call handling537      break;538    case Intrinsic::experimental_gc_statepoint:539      llvm_unreachable("statepoints don't produce pointers");540    case Intrinsic::experimental_gc_relocate:541      // Rerunning safepoint insertion after safepoints are already542      // inserted is not supported.  It could probably be made to work,543      // but why are you doing this?  There's no good reason.544      llvm_unreachable("repeat safepoint insertion is not supported");545    case Intrinsic::gcroot:546      // Currently, this mechanism hasn't been extended to work with gcroot.547      // There's no reason it couldn't be, but I haven't thought about the548      // implications much.549      llvm_unreachable(550          "interaction with the gcroot mechanism is not supported");551    case Intrinsic::experimental_gc_get_pointer_base:552      auto *BDV = findBaseDefiningValue(II->getOperand(0), Cache, KnownBases);553      Cache[II] = BDV;554      return BDV;555    }556  }557  // We assume that functions in the source language only return base558  // pointers.  This should probably be generalized via attributes to support559  // both source language and internal functions.560  if (isa<CallInst>(I) || isa<InvokeInst>(I)) {561    Cache[I] = I;562    setKnownBase(I, /* IsKnownBase */true, KnownBases);563    return I;564  }565 566  // TODO: I have absolutely no idea how to implement this part yet.  It's not567  // necessarily hard, I just haven't really looked at it yet.568  assert(!isa<LandingPadInst>(I) && "Landing Pad is unimplemented");569 570  if (isa<AtomicCmpXchgInst>(I)) {571    // A CAS is effectively a atomic store and load combined under a572    // predicate.  From the perspective of base pointers, we just treat it573    // like a load.574    Cache[I] = I;575    setKnownBase(I, /* IsKnownBase */true, KnownBases);576    return I;577  }578 579  if (isa<AtomicRMWInst>(I)) {580    assert(cast<AtomicRMWInst>(I)->getOperation() == AtomicRMWInst::Xchg &&581           "Only Xchg is allowed for pointer values");582    // A RMW Xchg is a combined atomic load and store, so we can treat the583    // loaded value as a base pointer.584    Cache[I] = I;585    setKnownBase(I, /* IsKnownBase */ true, KnownBases);586    return I;587  }588 589  // The aggregate ops.  Aggregates can either be in the heap or on the590  // stack, but in either case, this is simply a field load.  As a result,591  // this is a defining definition of the base just like a load is.592  if (isa<ExtractValueInst>(I)) {593    Cache[I] = I;594    setKnownBase(I, /* IsKnownBase */true, KnownBases);595    return I;596  }597 598  // We should never see an insert vector since that would require we be599  // tracing back a struct value not a pointer value.600  assert(!isa<InsertValueInst>(I) &&601         "Base pointer for a struct is meaningless");602 603  // This value might have been generated by findBasePointer() called when604  // substituting gc.get.pointer.base() intrinsic.605  bool IsKnownBase =606      isa<Instruction>(I) && cast<Instruction>(I)->getMetadata("is_base_value");607  setKnownBase(I, /* IsKnownBase */IsKnownBase, KnownBases);608  Cache[I] = I;609 610  // An extractelement produces a base result exactly when it's input does.611  // We may need to insert a parallel instruction to extract the appropriate612  // element out of the base vector corresponding to the input. Given this,613  // it's analogous to the phi and select case even though it's not a merge.614  if (isa<ExtractElementInst>(I))615    // Note: There a lot of obvious peephole cases here.  This are deliberately616    // handled after the main base pointer inference algorithm to make writing617    // test cases to exercise that code easier.618    return I;619 620  // The last two cases here don't return a base pointer.  Instead, they621  // return a value which dynamically selects from among several base622  // derived pointers (each with it's own base potentially).  It's the job of623  // the caller to resolve these.624  assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&625         "missing instruction case in findBaseDefiningValue");626  return I;627}628 629/// Returns the base defining value for this value.630static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache,631                                          IsKnownBaseMapTy &KnownBases) {632  if (!Cache.contains(I)) {633    auto *BDV = findBaseDefiningValue(I, Cache, KnownBases);634    Cache[I] = BDV;635    LLVM_DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> "636                      << Cache[I]->getName() << ", is known base = "637                      << KnownBases[I] << "\n");638  }639  assert(Cache[I] != nullptr);640  assert(KnownBases.contains(Cache[I]) &&641         "Cached value must be present in known bases map");642  return Cache[I];643}644 645/// Return a base pointer for this value if known.  Otherwise, return it's646/// base defining value.647static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache,648                            IsKnownBaseMapTy &KnownBases) {649  Value *Def = findBaseDefiningValueCached(I, Cache, KnownBases);650  auto Found = Cache.find(Def);651  if (Found != Cache.end()) {652    // Either a base-of relation, or a self reference.  Caller must check.653    return Found->second;654  }655  // Only a BDV available656  return Def;657}658 659#ifndef NDEBUG660/// This value is a base pointer that is not generated by RS4GC, i.e. it already661/// exists in the code.662static bool isOriginalBaseResult(Value *V) {663  // no recursion possible664  return !isa<PHINode>(V) && !isa<SelectInst>(V) &&665         !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&666         !isa<ShuffleVectorInst>(V);667}668#endif669 670static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases) {671  auto It = KnownBases.find(V);672  assert(It != KnownBases.end() && "Value not present in the map");673  return It->second;674}675 676static void setKnownBase(Value *V, bool IsKnownBase,677                         IsKnownBaseMapTy &KnownBases) {678#ifndef NDEBUG679  auto It = KnownBases.find(V);680  if (It != KnownBases.end())681    assert(It->second == IsKnownBase && "Changing already present value");682#endif683  KnownBases[V] = IsKnownBase;684}685 686// Returns true if First and Second values are both scalar or both vector.687static bool areBothVectorOrScalar(Value *First, Value *Second) {688  return isa<VectorType>(First->getType()) ==689         isa<VectorType>(Second->getType());690}691 692namespace {693 694/// Models the state of a single base defining value in the findBasePointer695/// algorithm for determining where a new instruction is needed to propagate696/// the base of this BDV.697class BDVState {698public:699  enum StatusTy {700     // Starting state of lattice701     Unknown,702     // Some specific base value -- does *not* mean that instruction703     // propagates the base of the object704     // ex: gep %arg, 16 -> %arg is the base value705     Base,706     // Need to insert a node to represent a merge.707     Conflict708  };709 710  BDVState() {711    llvm_unreachable("missing state in map");712  }713 714  explicit BDVState(Value *OriginalValue)715    : OriginalValue(OriginalValue) {}716  explicit BDVState(Value *OriginalValue, StatusTy Status, Value *BaseValue = nullptr)717    : OriginalValue(OriginalValue), Status(Status), BaseValue(BaseValue) {718    assert(Status != Base || BaseValue);719  }720 721  StatusTy getStatus() const { return Status; }722  Value *getOriginalValue() const { return OriginalValue; }723  Value *getBaseValue() const { return BaseValue; }724 725  bool isBase() const { return getStatus() == Base; }726  bool isUnknown() const { return getStatus() == Unknown; }727  bool isConflict() const { return getStatus() == Conflict; }728 729  // Values of type BDVState form a lattice, and this function implements the730  // meet731  // operation.732  void meet(const BDVState &Other) {733    auto markConflict = [&]() {734      Status = BDVState::Conflict;735      BaseValue = nullptr;736    };737    // Conflict is a final state.738    if (isConflict())739      return;740    // if we are not known - just take other state.741    if (isUnknown()) {742      Status = Other.getStatus();743      BaseValue = Other.getBaseValue();744      return;745    }746    // We are base.747    assert(isBase() && "Unknown state");748    // If other is unknown - just keep our state.749    if (Other.isUnknown())750      return;751    // If other is conflict - it is a final state.752    if (Other.isConflict())753      return markConflict();754    // Other is base as well.755    assert(Other.isBase() && "Unknown state");756    // If bases are different - Conflict.757    if (getBaseValue() != Other.getBaseValue())758      return markConflict();759    // We are identical, do nothing.760  }761 762  bool operator==(const BDVState &Other) const {763    return OriginalValue == Other.OriginalValue && BaseValue == Other.BaseValue &&764      Status == Other.Status;765  }766 767  bool operator!=(const BDVState &other) const { return !(*this == other); }768 769  LLVM_DUMP_METHOD770  void dump() const {771    print(dbgs());772    dbgs() << '\n';773  }774 775  void print(raw_ostream &OS) const {776    switch (getStatus()) {777    case Unknown:778      OS << "U";779      break;780    case Base:781      OS << "B";782      break;783    case Conflict:784      OS << "C";785      break;786    }787    OS << " (base " << getBaseValue() << " - "788       << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << ")"789       << " for  "  << OriginalValue->getName() << ":";790  }791 792private:793  AssertingVH<Value> OriginalValue; // instruction this state corresponds to794  StatusTy Status = Unknown;795  AssertingVH<Value> BaseValue = nullptr; // Non-null only if Status == Base.796};797 798} // end anonymous namespace799 800#ifndef NDEBUG801static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) {802  State.print(OS);803  return OS;804}805#endif806 807/// For a given value or instruction, figure out what base ptr its derived from.808/// For gc objects, this is simply itself.  On success, returns a value which is809/// the base pointer.  (This is reliable and can be used for relocation.)  On810/// failure, returns nullptr.811static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache,812                              IsKnownBaseMapTy &KnownBases) {813  Value *Def = findBaseOrBDV(I, Cache, KnownBases);814 815  if (isKnownBase(Def, KnownBases) && areBothVectorOrScalar(Def, I))816    return Def;817 818  // Here's the rough algorithm:819  // - For every SSA value, construct a mapping to either an actual base820  //   pointer or a PHI which obscures the base pointer.821  // - Construct a mapping from PHI to unknown TOP state.  Use an822  //   optimistic algorithm to propagate base pointer information.  Lattice823  //   looks like:824  //   UNKNOWN825  //   b1 b2 b3 b4826  //   CONFLICT827  //   When algorithm terminates, all PHIs will either have a single concrete828  //   base or be in a conflict state.829  // - For every conflict, insert a dummy PHI node without arguments.  Add830  //   these to the base[Instruction] = BasePtr mapping.  For every831  //   non-conflict, add the actual base.832  //  - For every conflict, add arguments for the base[a] of each input833  //   arguments.834  //835  // Note: A simpler form of this would be to add the conflict form of all836  // PHIs without running the optimistic algorithm.  This would be837  // analogous to pessimistic data flow and would likely lead to an838  // overall worse solution.839 840#ifndef NDEBUG841  auto isExpectedBDVType = [](Value *BDV) {842    return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||843           isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||844           isa<ShuffleVectorInst>(BDV);845  };846#endif847 848  // Once populated, will contain a mapping from each potentially non-base BDV849  // to a lattice value (described above) which corresponds to that BDV.850  // We use the order of insertion (DFS over the def/use graph) to provide a851  // stable deterministic ordering for visiting DenseMaps (which are unordered)852  // below.  This is important for deterministic compilation.853  MapVector<Value *, BDVState> States;854 855#ifndef NDEBUG856  auto VerifyStates = [&]() {857    for (auto &Entry : States) {858      assert(Entry.first == Entry.second.getOriginalValue());859    }860  };861#endif862 863  auto visitBDVOperands = [](Value *BDV, std::function<void (Value*)> F) {864    if (PHINode *PN = dyn_cast<PHINode>(BDV)) {865      for (Value *InVal : PN->incoming_values())866        F(InVal);867    } else if (SelectInst *SI = dyn_cast<SelectInst>(BDV)) {868      F(SI->getTrueValue());869      F(SI->getFalseValue());870    } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) {871      F(EE->getVectorOperand());872    } else if (auto *IE = dyn_cast<InsertElementInst>(BDV)) {873      F(IE->getOperand(0));874      F(IE->getOperand(1));875    } else if (auto *SV = dyn_cast<ShuffleVectorInst>(BDV)) {876      // For a canonical broadcast, ignore the undef argument877      // (without this, we insert a parallel base shuffle for every broadcast)878      F(SV->getOperand(0));879      if (!SV->isZeroEltSplat())880        F(SV->getOperand(1));881    } else {882      llvm_unreachable("unexpected BDV type");883    }884  };885 886 887  // Recursively fill in all base defining values reachable from the initial888  // one for which we don't already know a definite base value for889  /* scope */ {890    SmallVector<Value*, 16> Worklist;891    Worklist.push_back(Def);892    States.insert({Def, BDVState(Def)});893    while (!Worklist.empty()) {894      Value *Current = Worklist.pop_back_val();895      assert(!isOriginalBaseResult(Current) && "why did it get added?");896 897      auto visitIncomingValue = [&](Value *InVal) {898        Value *Base = findBaseOrBDV(InVal, Cache, KnownBases);899        if (isKnownBase(Base, KnownBases) && areBothVectorOrScalar(Base, InVal))900          // Known bases won't need new instructions introduced and can be901          // ignored safely. However, this can only be done when InVal and Base902          // are both scalar or both vector. Otherwise, we need to find a903          // correct BDV for InVal, by creating an entry in the lattice904          // (States).905          return;906        assert(isExpectedBDVType(Base) && "the only non-base values "907               "we see should be base defining values");908        if (States.insert(std::make_pair(Base, BDVState(Base))).second)909          Worklist.push_back(Base);910      };911 912      visitBDVOperands(Current, visitIncomingValue);913    }914  }915 916#ifndef NDEBUG917  VerifyStates();918  LLVM_DEBUG(dbgs() << "States after initialization:\n");919  for (const auto &Pair : States) {920    LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");921  }922#endif923 924  // Iterate forward through the value graph pruning any node from the state925  // list where all of the inputs are base pointers.  The purpose of this is to926  // reuse existing values when the derived pointer we were asked to materialize927  // a base pointer for happens to be a base pointer itself.  (Or a sub-graph928  // feeding it does.)929  SmallVector<Value *> ToRemove;930  do {931    ToRemove.clear();932    for (auto Pair : States) {933      Value *BDV = Pair.first;934      auto canPruneInput = [&](Value *V) {935        // If the input of the BDV is the BDV itself we can prune it. This is936        // only possible if the BDV is a PHI node.937        if (V->stripPointerCasts() == BDV)938          return true;939        Value *VBDV = findBaseOrBDV(V, Cache, KnownBases);940        if (V->stripPointerCasts() != VBDV)941          return false;942        // The assumption is that anything not in the state list is943        // propagates a base pointer.944        return States.count(VBDV) == 0;945      };946 947      bool CanPrune = true;948      visitBDVOperands(BDV, [&](Value *Op) {949        CanPrune = CanPrune && canPruneInput(Op);950      });951      if (CanPrune)952        ToRemove.push_back(BDV);953    }954    for (Value *V : ToRemove) {955      States.erase(V);956      // Cache the fact V is it's own base for later usage.957      Cache[V] = V;958    }959  } while (!ToRemove.empty());960 961  // Did we manage to prove that Def itself must be a base pointer?962  if (!States.count(Def))963    return Def;964 965  // Return a phi state for a base defining value.  We'll generate a new966  // base state for known bases and expect to find a cached state otherwise.967  auto GetStateForBDV = [&](Value *BaseValue, Value *Input) {968    auto I = States.find(BaseValue);969    if (I != States.end())970      return I->second;971    assert(areBothVectorOrScalar(BaseValue, Input));972    return BDVState(BaseValue, BDVState::Base, BaseValue);973  };974 975  // Even though we have identified a concrete base (or a conflict) for all live976  // pointers at this point, there are cases where the base is of an977  // incompatible type compared to the original instruction. We conservatively978  // mark those as conflicts to ensure that corresponding BDVs will be generated979  // in the next steps.980 981  // this is a rather explicit check for all cases where we should mark the982  // state as a conflict to force the latter stages of the algorithm to emit983  // the BDVs.984  // TODO: in many cases the instructions emited for the conflicting states985  // will be identical to the I itself (if the I's operate on their BDVs986  // themselves). We should exploit this, but can't do it here since it would987  // break the invariant about the BDVs not being known to be a base.988  // TODO: the code also does not handle constants at all - the algorithm relies989  // on all constants having the same BDV and therefore constant-only insns990  // will never be in conflict, but this check is ignored here. If the991  // constant conflicts will be to BDVs themselves, they will be identical992  // instructions and will get optimized away (as in the above TODO)993  auto MarkConflict = [&](Instruction *I, Value *BaseValue) {994    // II and EE mixes vector & scalar so is always a conflict995    if (isa<InsertElementInst>(I) || isa<ExtractElementInst>(I))996      return true;997    // Shuffle vector is always a conflict as it creates new vector from998    // existing ones.999    if (isa<ShuffleVectorInst>(I))1000      return true;1001    // Any  instructions where the computed base type differs from the1002    // instruction type. An example is where an extract instruction is used by a1003    // select. Here the select's BDV is a vector (because of extract's BDV),1004    // while the select itself is a scalar type. Note that the IE and EE1005    // instruction check is not fully subsumed by the vector<->scalar check at1006    // the end, this is due to the BDV algorithm being ignorant of BDV types at1007    // this junction.1008    if (!areBothVectorOrScalar(BaseValue, I))1009      return true;1010    return false;1011  };1012 1013  bool Progress = true;1014  while (Progress) {1015#ifndef NDEBUG1016    const size_t OldSize = States.size();1017#endif1018    Progress = false;1019    // We're only changing values in this loop, thus safe to keep iterators.1020    // Since this is computing a fixed point, the order of visit does not1021    // effect the result.  TODO: We could use a worklist here and make this run1022    // much faster.1023    for (auto Pair : States) {1024      Value *BDV = Pair.first;1025      // Only values that do not have known bases or those that have differing1026      // type (scalar versus vector) from a possible known base should be in the1027      // lattice.1028      assert((!isKnownBase(BDV, KnownBases) ||1029             !areBothVectorOrScalar(BDV, Pair.second.getBaseValue())) &&1030                 "why did it get added?");1031 1032      BDVState NewState(BDV);1033      visitBDVOperands(BDV, [&](Value *Op) {1034        Value *BDV = findBaseOrBDV(Op, Cache, KnownBases);1035        auto OpState = GetStateForBDV(BDV, Op);1036        NewState.meet(OpState);1037      });1038 1039      // if the instruction has known base, but should in fact be marked as1040      // conflict because of incompatible in/out types, we mark it as such1041      // ensuring that it will propagate through the fixpoint iteration1042      auto I = cast<Instruction>(BDV);1043      auto BV = NewState.getBaseValue();1044      if (BV && MarkConflict(I, BV))1045        NewState = BDVState(I, BDVState::Conflict);1046 1047      BDVState OldState = Pair.second;1048      if (OldState != NewState) {1049        Progress = true;1050        States[BDV] = NewState;1051      }1052    }1053 1054    assert(OldSize == States.size() &&1055           "fixed point shouldn't be adding any new nodes to state");1056  }1057 1058#ifndef NDEBUG1059  VerifyStates();1060  LLVM_DEBUG(dbgs() << "States after meet iteration:\n");1061  for (const auto &Pair : States) {1062    LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");1063  }1064 1065  // since we do the conflict marking as part of the fixpoint iteration this1066  // loop only asserts that invariants are met1067  for (auto Pair : States) {1068    Instruction *I = cast<Instruction>(Pair.first);1069    BDVState State = Pair.second;1070    auto *BaseValue = State.getBaseValue();1071    // Only values that do not have known bases or those that have differing1072    // type (scalar versus vector) from a possible known base should be in the1073    // lattice.1074    assert(1075        (!isKnownBase(I, KnownBases) || !areBothVectorOrScalar(I, BaseValue)) &&1076        "why did it get added?");1077    assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");1078  }1079#endif1080 1081  // Insert Phis for all conflicts1082  // TODO: adjust naming patterns to avoid this order of iteration dependency1083  for (auto Pair : States) {1084    Instruction *I = cast<Instruction>(Pair.first);1085    BDVState State = Pair.second;1086    // Only values that do not have known bases or those that have differing1087    // type (scalar versus vector) from a possible known base should be in the1088    // lattice.1089    assert((!isKnownBase(I, KnownBases) ||1090            !areBothVectorOrScalar(I, State.getBaseValue())) &&1091           "why did it get added?");1092    assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");1093 1094    // Since we're joining a vector and scalar base, they can never be the1095    // same.  As a result, we should always see insert element having reached1096    // the conflict state.1097    assert(!isa<InsertElementInst>(I) || State.isConflict());1098 1099    if (!State.isConflict())1100      continue;1101 1102    auto getMangledName = [](Instruction *I) -> std::string {1103      if (isa<PHINode>(I)) {1104        return suffixed_name_or(I, ".base", "base_phi");1105      } else if (isa<SelectInst>(I)) {1106        return suffixed_name_or(I, ".base", "base_select");1107      } else if (isa<ExtractElementInst>(I)) {1108        return suffixed_name_or(I, ".base", "base_ee");1109      } else if (isa<InsertElementInst>(I)) {1110        return suffixed_name_or(I, ".base", "base_ie");1111      } else {1112        return suffixed_name_or(I, ".base", "base_sv");1113      }1114    };1115 1116    Instruction *BaseInst = I->clone();1117    BaseInst->insertBefore(I->getIterator());1118    BaseInst->setName(getMangledName(I));1119    // Add metadata marking this as a base value1120    BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));1121    States[I] = BDVState(I, BDVState::Conflict, BaseInst);1122    setKnownBase(BaseInst, /* IsKnownBase */true, KnownBases);1123  }1124 1125#ifndef NDEBUG1126  VerifyStates();1127#endif1128 1129  // Returns a instruction which produces the base pointer for a given1130  // instruction.  The instruction is assumed to be an input to one of the BDVs1131  // seen in the inference algorithm above.  As such, we must either already1132  // know it's base defining value is a base, or have inserted a new1133  // instruction to propagate the base of it's BDV and have entered that newly1134  // introduced instruction into the state table.  In either case, we are1135  // assured to be able to determine an instruction which produces it's base1136  // pointer.1137  auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) {1138    Value *BDV = findBaseOrBDV(Input, Cache, KnownBases);1139    Value *Base = nullptr;1140    if (auto It = States.find(BDV); It == States.end()) {1141      assert(areBothVectorOrScalar(BDV, Input));1142      Base = BDV;1143    } else {1144      // Either conflict or base.1145      Base = It->second.getBaseValue();1146    }1147    assert(Base && "Can't be null");1148    // The cast is needed since base traversal may strip away bitcasts1149    if (Base->getType() != Input->getType() && InsertPt)1150      Base = new BitCastInst(Base, Input->getType(), "cast",1151                             InsertPt->getIterator());1152    return Base;1153  };1154 1155  // Fixup all the inputs of the new PHIs.  Visit order needs to be1156  // deterministic and predictable because we're naming newly created1157  // instructions.1158  for (auto Pair : States) {1159    Instruction *BDV = cast<Instruction>(Pair.first);1160    BDVState State = Pair.second;1161 1162    // Only values that do not have known bases or those that have differing1163    // type (scalar versus vector) from a possible known base should be in the1164    // lattice.1165    assert((!isKnownBase(BDV, KnownBases) ||1166            !areBothVectorOrScalar(BDV, State.getBaseValue())) &&1167           "why did it get added?");1168    assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");1169    if (!State.isConflict())1170      continue;1171 1172    if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {1173      PHINode *PN = cast<PHINode>(BDV);1174      const unsigned NumPHIValues = PN->getNumIncomingValues();1175 1176      // The IR verifier requires phi nodes with multiple entries from the1177      // same basic block to have the same incoming value for each of those1178      // entries.  Since we're inserting bitcasts in the loop, make sure we1179      // do so at least once per incoming block.1180      DenseMap<BasicBlock *, Value*> BlockToValue;1181      for (unsigned i = 0; i < NumPHIValues; i++) {1182        Value *InVal = PN->getIncomingValue(i);1183        BasicBlock *InBB = PN->getIncomingBlock(i);1184        auto [It, Inserted] = BlockToValue.try_emplace(InBB);1185        if (Inserted)1186          It->second = getBaseForInput(InVal, InBB->getTerminator());1187        else {1188#ifndef NDEBUG1189          Value *OldBase = It->second;1190          Value *Base = getBaseForInput(InVal, nullptr);1191 1192          // We can't use `stripPointerCasts` instead of this function because1193          // `stripPointerCasts` doesn't handle vectors of pointers.1194          auto StripBitCasts = [](Value *V) -> Value * {1195            while (auto *BC = dyn_cast<BitCastInst>(V))1196              V = BC->getOperand(0);1197            return V;1198          };1199          // In essence this assert states: the only way two values1200          // incoming from the same basic block may be different is by1201          // being different bitcasts of the same value.  A cleanup1202          // that remains TODO is changing findBaseOrBDV to return an1203          // llvm::Value of the correct type (and still remain pure).1204          // This will remove the need to add bitcasts.1205          assert(StripBitCasts(Base) == StripBitCasts(OldBase) &&1206                 "findBaseOrBDV should be pure!");1207#endif1208        }1209        Value *Base = It->second;1210        BasePHI->setIncomingValue(i, Base);1211      }1212    } else if (SelectInst *BaseSI =1213                   dyn_cast<SelectInst>(State.getBaseValue())) {1214      SelectInst *SI = cast<SelectInst>(BDV);1215 1216      // Find the instruction which produces the base for each input.1217      // We may need to insert a bitcast.1218      BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));1219      BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));1220    } else if (auto *BaseEE =1221                   dyn_cast<ExtractElementInst>(State.getBaseValue())) {1222      Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();1223      // Find the instruction which produces the base for each input.  We may1224      // need to insert a bitcast.1225      BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));1226    } else if (auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){1227      auto *BdvIE = cast<InsertElementInst>(BDV);1228      auto UpdateOperand = [&](int OperandIdx) {1229        Value *InVal = BdvIE->getOperand(OperandIdx);1230        Value *Base = getBaseForInput(InVal, BaseIE);1231        BaseIE->setOperand(OperandIdx, Base);1232      };1233      UpdateOperand(0); // vector operand1234      UpdateOperand(1); // scalar operand1235    } else {1236      auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());1237      auto *BdvSV = cast<ShuffleVectorInst>(BDV);1238      auto UpdateOperand = [&](int OperandIdx) {1239        Value *InVal = BdvSV->getOperand(OperandIdx);1240        Value *Base = getBaseForInput(InVal, BaseSV);1241        BaseSV->setOperand(OperandIdx, Base);1242      };1243      UpdateOperand(0); // vector operand1244      if (!BdvSV->isZeroEltSplat())1245        UpdateOperand(1); // vector operand1246      else {1247        // Never read, so just use poison1248        Value *InVal = BdvSV->getOperand(1);1249        BaseSV->setOperand(1, PoisonValue::get(InVal->getType()));1250      }1251    }1252  }1253 1254#ifndef NDEBUG1255  VerifyStates();1256#endif1257 1258  // get the data layout to compare the sizes of base/derived pointer values1259  [[maybe_unused]] auto &DL =1260      cast<llvm::Instruction>(Def)->getDataLayout();1261  // Cache all of our results so we can cheaply reuse them1262  // NOTE: This is actually two caches: one of the base defining value1263  // relation and one of the base pointer relation!  FIXME1264  for (auto Pair : States) {1265    auto *BDV = Pair.first;1266    Value *Base = Pair.second.getBaseValue();1267    assert(BDV && Base);1268    // Whenever we have a derived ptr(s), their base1269    // ptr(s) must be of the same size, not necessarily the same type1270    assert(DL.getTypeAllocSize(BDV->getType()) ==1271               DL.getTypeAllocSize(Base->getType()) &&1272           "Derived and base values should have same size");1273    // Only values that do not have known bases or those that have differing1274    // type (scalar versus vector) from a possible known base should be in the1275    // lattice.1276    assert(1277        (!isKnownBase(BDV, KnownBases) || !areBothVectorOrScalar(BDV, Base)) &&1278        "why did it get added?");1279 1280    LLVM_DEBUG(1281        dbgs() << "Updating base value cache"1282               << " for: " << BDV->getName() << " from: "1283               << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none")1284               << " to: " << Base->getName() << "\n");1285 1286    Cache[BDV] = Base;1287  }1288  assert(Cache.count(Def));1289  return Cache[Def];1290}1291 1292// For a set of live pointers (base and/or derived), identify the base1293// pointer of the object which they are derived from.  This routine will1294// mutate the IR graph as needed to make the 'base' pointer live at the1295// definition site of 'derived'.  This ensures that any use of 'derived' can1296// also use 'base'.  This may involve the insertion of a number of1297// additional PHI nodes.1298//1299// preconditions: live is a set of pointer type Values1300//1301// side effects: may insert PHI nodes into the existing CFG, will preserve1302// CFG, will not remove or mutate any existing nodes1303//1304// post condition: PointerToBase contains one (derived, base) pair for every1305// pointer in live.  Note that derived can be equal to base if the original1306// pointer was a base pointer.1307static void findBasePointers(const StatepointLiveSetTy &live,1308                             PointerToBaseTy &PointerToBase, DominatorTree *DT,1309                             DefiningValueMapTy &DVCache,1310                             IsKnownBaseMapTy &KnownBases) {1311  for (Value *ptr : live) {1312    Value *base = findBasePointer(ptr, DVCache, KnownBases);1313    assert(base && "failed to find base pointer");1314    PointerToBase[ptr] = base;1315    assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||1316            DT->dominates(cast<Instruction>(base)->getParent(),1317                          cast<Instruction>(ptr)->getParent())) &&1318           "The base we found better dominate the derived pointer");1319  }1320}1321 1322/// Find the required based pointers (and adjust the live set) for the given1323/// parse point.1324static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache,1325                             CallBase *Call,1326                             PartiallyConstructedSafepointRecord &result,1327                             PointerToBaseTy &PointerToBase,1328                             IsKnownBaseMapTy &KnownBases) {1329  StatepointLiveSetTy PotentiallyDerivedPointers = result.LiveSet;1330  // We assume that all pointers passed to deopt are base pointers; as an1331  // optimization, we can use this to avoid separately materializing the base1332  // pointer graph.  This is only relevant since we're very conservative about1333  // generating new conflict nodes during base pointer insertion.  If we were1334  // smarter there, this would be irrelevant.1335  if (auto Opt = Call->getOperandBundle(LLVMContext::OB_deopt))1336    for (Value *V : Opt->Inputs) {1337      if (!PotentiallyDerivedPointers.count(V))1338        continue;1339      PotentiallyDerivedPointers.remove(V);1340      PointerToBase[V] = V;1341    }1342  findBasePointers(PotentiallyDerivedPointers, PointerToBase, &DT, DVCache,1343                   KnownBases);1344}1345 1346/// Given an updated version of the dataflow liveness results, update the1347/// liveset and base pointer maps for the call site CS.1348static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,1349                                  CallBase *Call,1350                                  PartiallyConstructedSafepointRecord &result,1351                                  PointerToBaseTy &PointerToBase,1352                                  GCStrategy *GC);1353 1354static void recomputeLiveInValues(1355    Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,1356    MutableArrayRef<struct PartiallyConstructedSafepointRecord> records,1357    PointerToBaseTy &PointerToBase, GCStrategy *GC) {1358  // TODO-PERF: reuse the original liveness, then simply run the dataflow1359  // again.  The old values are still live and will help it stabilize quickly.1360  GCPtrLivenessData RevisedLivenessData;1361  computeLiveInValues(DT, F, RevisedLivenessData, GC);1362  for (size_t i = 0; i < records.size(); i++) {1363    struct PartiallyConstructedSafepointRecord &info = records[i];1364    recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info, PointerToBase,1365                          GC);1366  }1367}1368 1369// Utility function which clones all instructions from "ChainToBase"1370// and inserts them before "InsertBefore". Returns rematerialized value1371// which should be used after statepoint.1372static Instruction *rematerializeChain(ArrayRef<Instruction *> ChainToBase,1373                                       BasicBlock::iterator InsertBefore,1374                                       Value *RootOfChain,1375                                       Value *AlternateLiveBase) {1376  Instruction *LastClonedValue = nullptr;1377  Instruction *LastValue = nullptr;1378  // Walk backwards to visit top-most instructions first.1379  for (Instruction *Instr : reverse(ChainToBase)) {1380    // Only GEP's and casts are supported as we need to be careful to not1381    // introduce any new uses of pointers not in the liveset.1382    // Note that it's fine to introduce new uses of pointers which were1383    // otherwise not used after this statepoint.1384    assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));1385 1386    Instruction *ClonedValue = Instr->clone();1387    ClonedValue->insertBefore(InsertBefore);1388    ClonedValue->setName(Instr->getName() + ".remat");1389 1390    // If it is not first instruction in the chain then it uses previously1391    // cloned value. We should update it to use cloned value.1392    if (LastClonedValue) {1393      assert(LastValue);1394      ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue);1395#ifndef NDEBUG1396      for (auto *OpValue : ClonedValue->operand_values()) {1397        // Assert that cloned instruction does not use any instructions from1398        // this chain other than LastClonedValue1399        assert(!is_contained(ChainToBase, OpValue) &&1400               "incorrect use in rematerialization chain");1401        // Assert that the cloned instruction does not use the RootOfChain1402        // or the AlternateLiveBase.1403        assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);1404      }1405#endif1406    } else {1407      // For the first instruction, replace the use of unrelocated base i.e.1408      // RootOfChain/OrigRootPhi, with the corresponding PHI present in the1409      // live set. They have been proved to be the same PHI nodes.  Note1410      // that the *only* use of the RootOfChain in the ChainToBase list is1411      // the first Value in the list.1412      if (RootOfChain != AlternateLiveBase)1413        ClonedValue->replaceUsesOfWith(RootOfChain, AlternateLiveBase);1414    }1415 1416    LastClonedValue = ClonedValue;1417    LastValue = Instr;1418  }1419  assert(LastClonedValue);1420  return LastClonedValue;1421}1422 1423// When inserting gc.relocate and gc.result calls, we need to ensure there are1424// no uses of the original value / return value between the gc.statepoint and1425// the gc.relocate / gc.result call.  One case which can arise is a phi node1426// starting one of the successor blocks.  We also need to be able to insert the1427// gc.relocates only on the path which goes through the statepoint.  We might1428// need to split an edge to make this possible.1429static BasicBlock *1430normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent,1431                            DominatorTree &DT) {1432  BasicBlock *Ret = BB;1433  if (!BB->getUniquePredecessor())1434    Ret = SplitBlockPredecessors(BB, InvokeParent, "", &DT);1435 1436  // Now that 'Ret' has unique predecessor we can safely remove all phi nodes1437  // from it1438  FoldSingleEntryPHINodes(Ret);1439  assert(!isa<PHINode>(Ret->begin()) &&1440         "All PHI nodes should have been removed!");1441 1442  // At this point, we can safely insert a gc.relocate or gc.result as the first1443  // instruction in Ret if needed.1444  return Ret;1445}1446 1447// List of all function attributes which must be stripped when lowering from1448// abstract machine model to physical machine model.  Essentially, these are1449// all the effects a safepoint might have which we ignored in the abstract1450// machine model for purposes of optimization.  We have to strip these on1451// both function declarations and call sites.1452static constexpr Attribute::AttrKind FnAttrsToStrip[] =1453  {Attribute::Memory, Attribute::NoSync, Attribute::NoFree};1454 1455// Create new attribute set containing only attributes which can be transferred1456// from the original call to the safepoint.1457static AttributeList legalizeCallAttributes(CallBase *Call, bool IsMemIntrinsic,1458                                            AttributeList StatepointAL) {1459  AttributeList OrigAL = Call->getAttributes();1460  if (OrigAL.isEmpty())1461    return StatepointAL;1462 1463  // Remove the readonly, readnone, and statepoint function attributes.1464  LLVMContext &Ctx = Call->getContext();1465  AttrBuilder FnAttrs(Ctx, OrigAL.getFnAttrs());1466  for (auto Attr : FnAttrsToStrip)1467    FnAttrs.removeAttribute(Attr);1468 1469  for (Attribute A : OrigAL.getFnAttrs()) {1470    if (isStatepointDirectiveAttr(A))1471      FnAttrs.removeAttribute(A);1472  }1473 1474  StatepointAL = StatepointAL.addFnAttributes(Ctx, FnAttrs);1475 1476  // The memory intrinsics do not have a 1:1 correspondence of the original1477  // call arguments to the produced statepoint. Do not transfer the argument1478  // attributes to avoid putting them on incorrect arguments.1479  if (IsMemIntrinsic)1480    return StatepointAL;1481 1482  // Attach the argument attributes from the original call at the corresponding1483  // arguments in the statepoint. Note that any argument attributes that are1484  // invalid after lowering are stripped in stripNonValidDataFromBody.1485  for (unsigned I : llvm::seq(Call->arg_size()))1486    StatepointAL = StatepointAL.addParamAttributes(1487        Ctx, GCStatepointInst::CallArgsBeginPos + I,1488        AttrBuilder(Ctx, OrigAL.getParamAttrs(I)));1489 1490  // Return attributes are later attached to the gc.result intrinsic.1491  return StatepointAL;1492}1493 1494/// Helper function to place all gc relocates necessary for the given1495/// statepoint.1496/// Inputs:1497///   liveVariables - list of variables to be relocated.1498///   basePtrs - base pointers.1499///   statepointToken - statepoint instruction to which relocates should be1500///   bound.1501///   Builder - Llvm IR builder to be used to construct new calls.1502static void CreateGCRelocates(ArrayRef<Value *> LiveVariables,1503                              ArrayRef<Value *> BasePtrs,1504                              Instruction *StatepointToken,1505                              IRBuilder<> &Builder, GCStrategy *GC) {1506  if (LiveVariables.empty())1507    return;1508 1509  auto FindIndex = [](ArrayRef<Value *> LiveVec, Value *Val) {1510    auto ValIt = llvm::find(LiveVec, Val);1511    assert(ValIt != LiveVec.end() && "Val not found in LiveVec!");1512    size_t Index = std::distance(LiveVec.begin(), ValIt);1513    assert(Index < LiveVec.size() && "Bug in std::find?");1514    return Index;1515  };1516  Module *M = StatepointToken->getModule();1517 1518  // All gc_relocate are generated as i8 addrspace(1)* (or a vector type whose1519  // element type is i8 addrspace(1)*). We originally generated unique1520  // declarations for each pointer type, but this proved problematic because1521  // the intrinsic mangling code is incomplete and fragile.  Since we're moving1522  // towards a single unified pointer type anyways, we can just cast everything1523  // to an i8* of the right address space.  A bitcast is added later to convert1524  // gc_relocate to the actual value's type.1525  auto getGCRelocateDecl = [&](Type *Ty) {1526    assert(isHandledGCPointerType(Ty, GC));1527    auto AS = Ty->getScalarType()->getPointerAddressSpace();1528    Type *NewTy = PointerType::get(M->getContext(), AS);1529    if (auto *VT = dyn_cast<VectorType>(Ty))1530      NewTy = FixedVectorType::get(NewTy,1531                                   cast<FixedVectorType>(VT)->getNumElements());1532    return Intrinsic::getOrInsertDeclaration(1533        M, Intrinsic::experimental_gc_relocate, {NewTy});1534  };1535 1536  // Lazily populated map from input types to the canonicalized form mentioned1537  // in the comment above.  This should probably be cached somewhere more1538  // broadly.1539  DenseMap<Type *, Function *> TypeToDeclMap;1540 1541  for (unsigned i = 0; i < LiveVariables.size(); i++) {1542    // Generate the gc.relocate call and save the result1543    Value *BaseIdx = Builder.getInt32(FindIndex(LiveVariables, BasePtrs[i]));1544    Value *LiveIdx = Builder.getInt32(i);1545 1546    Type *Ty = LiveVariables[i]->getType();1547    auto [It, Inserted] = TypeToDeclMap.try_emplace(Ty);1548    if (Inserted)1549      It->second = getGCRelocateDecl(Ty);1550    Function *GCRelocateDecl = It->second;1551 1552    // only specify a debug name if we can give a useful one1553    CallInst *Reloc = Builder.CreateCall(1554        GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},1555        suffixed_name_or(LiveVariables[i], ".relocated", ""));1556    // Trick CodeGen into thinking there are lots of free registers at this1557    // fake call.1558    Reloc->setCallingConv(CallingConv::Cold);1559  }1560}1561 1562namespace {1563 1564/// This struct is used to defer RAUWs and `eraseFromParent` s.  Using this1565/// avoids having to worry about keeping around dangling pointers to Values.1566class DeferredReplacement {1567  AssertingVH<Instruction> Old;1568  AssertingVH<Instruction> New;1569  bool IsDeoptimize = false;1570 1571  DeferredReplacement() = default;1572 1573public:1574  static DeferredReplacement createRAUW(Instruction *Old, Instruction *New) {1575    assert(Old != New && Old && New &&1576           "Cannot RAUW equal values or to / from null!");1577 1578    DeferredReplacement D;1579    D.Old = Old;1580    D.New = New;1581    return D;1582  }1583 1584  static DeferredReplacement createDelete(Instruction *ToErase) {1585    DeferredReplacement D;1586    D.Old = ToErase;1587    return D;1588  }1589 1590  static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) {1591#ifndef NDEBUG1592    auto *F = cast<CallInst>(Old)->getCalledFunction();1593    assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&1594           "Only way to construct a deoptimize deferred replacement");1595#endif1596    DeferredReplacement D;1597    D.Old = Old;1598    D.IsDeoptimize = true;1599    return D;1600  }1601 1602  /// Does the task represented by this instance.1603  void doReplacement() {1604    Instruction *OldI = Old;1605    Instruction *NewI = New;1606 1607    assert(OldI != NewI && "Disallowed at construction?!");1608    assert((!IsDeoptimize || !New) &&1609           "Deoptimize intrinsics are not replaced!");1610 1611    Old = nullptr;1612    New = nullptr;1613 1614    if (NewI)1615      OldI->replaceAllUsesWith(NewI);1616 1617    if (IsDeoptimize) {1618      // Note: we've inserted instructions, so the call to llvm.deoptimize may1619      // not necessarily be followed by the matching return.1620      auto *RI = cast<ReturnInst>(OldI->getParent()->getTerminator());1621      new UnreachableInst(RI->getContext(), RI->getIterator());1622      RI->eraseFromParent();1623    }1624 1625    OldI->eraseFromParent();1626  }1627};1628 1629} // end anonymous namespace1630 1631static StringRef getDeoptLowering(CallBase *Call) {1632  const char *DeoptLowering = "deopt-lowering";1633  if (Call->hasFnAttr(DeoptLowering)) {1634    // FIXME: Calls have a *really* confusing interface around attributes1635    // with values.1636    const AttributeList &CSAS = Call->getAttributes();1637    if (CSAS.hasFnAttr(DeoptLowering))1638      return CSAS.getFnAttr(DeoptLowering).getValueAsString();1639    Function *F = Call->getCalledFunction();1640    assert(F && F->hasFnAttribute(DeoptLowering));1641    return F->getFnAttribute(DeoptLowering).getValueAsString();1642  }1643  return "live-through";1644}1645 1646static void1647makeStatepointExplicitImpl(CallBase *Call, /* to replace */1648                           const SmallVectorImpl<Value *> &BasePtrs,1649                           const SmallVectorImpl<Value *> &LiveVariables,1650                           PartiallyConstructedSafepointRecord &Result,1651                           std::vector<DeferredReplacement> &Replacements,1652                           const PointerToBaseTy &PointerToBase,1653                           GCStrategy *GC) {1654  assert(BasePtrs.size() == LiveVariables.size());1655 1656  // Then go ahead and use the builder do actually do the inserts.  We insert1657  // immediately before the previous instruction under the assumption that all1658  // arguments will be available here.  We can't insert afterwards since we may1659  // be replacing a terminator.1660  IRBuilder<> Builder(Call);1661 1662  ArrayRef<Value *> GCLive(LiveVariables);1663  uint64_t StatepointID = StatepointDirectives::DefaultStatepointID;1664  uint32_t NumPatchBytes = 0;1665  uint32_t Flags = uint32_t(StatepointFlags::None);1666 1667  SmallVector<Value *, 8> CallArgs(Call->args());1668  std::optional<ArrayRef<Use>> DeoptArgs;1669  if (auto Bundle = Call->getOperandBundle(LLVMContext::OB_deopt))1670    DeoptArgs = Bundle->Inputs;1671  std::optional<ArrayRef<Use>> TransitionArgs;1672  if (auto Bundle = Call->getOperandBundle(LLVMContext::OB_gc_transition)) {1673    TransitionArgs = Bundle->Inputs;1674    // TODO: This flag no longer serves a purpose and can be removed later1675    Flags |= uint32_t(StatepointFlags::GCTransition);1676  }1677 1678  // Instead of lowering calls to @llvm.experimental.deoptimize as normal calls1679  // with a return value, we lower then as never returning calls to1680  // __llvm_deoptimize that are followed by unreachable to get better codegen.1681  bool IsDeoptimize = false;1682  bool IsMemIntrinsic = false;1683 1684  StatepointDirectives SD =1685      parseStatepointDirectivesFromAttrs(Call->getAttributes());1686  if (SD.NumPatchBytes)1687    NumPatchBytes = *SD.NumPatchBytes;1688  if (SD.StatepointID)1689    StatepointID = *SD.StatepointID;1690 1691  // Pass through the requested lowering if any.  The default is live-through.1692  StringRef DeoptLowering = getDeoptLowering(Call);1693  if (DeoptLowering == "live-in")1694    Flags |= uint32_t(StatepointFlags::DeoptLiveIn);1695  else {1696    assert(DeoptLowering == "live-through" && "Unsupported value!");1697  }1698 1699  FunctionCallee CallTarget(Call->getFunctionType(), Call->getCalledOperand());1700  if (Function *F = dyn_cast<Function>(CallTarget.getCallee())) {1701    auto IID = F->getIntrinsicID();1702    if (IID == Intrinsic::experimental_deoptimize) {1703      // Calls to llvm.experimental.deoptimize are lowered to calls to the1704      // __llvm_deoptimize symbol.  We want to resolve this now, since the1705      // verifier does not allow taking the address of an intrinsic function.1706 1707      SmallVector<Type *, 8> DomainTy;1708      for (Value *Arg : CallArgs)1709        DomainTy.push_back(Arg->getType());1710      auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,1711                                    /* isVarArg = */ false);1712 1713      // Note: CallTarget can be a bitcast instruction of a symbol if there are1714      // calls to @llvm.experimental.deoptimize with different argument types in1715      // the same module.  This is fine -- we assume the frontend knew what it1716      // was doing when generating this kind of IR.1717      CallTarget = F->getParent()1718                       ->getOrInsertFunction("__llvm_deoptimize", FTy);1719 1720      IsDeoptimize = true;1721    } else if (IID == Intrinsic::memcpy_element_unordered_atomic ||1722               IID == Intrinsic::memmove_element_unordered_atomic) {1723      IsMemIntrinsic = true;1724 1725      // Unordered atomic memcpy and memmove intrinsics which are not explicitly1726      // marked as "gc-leaf-function" should be lowered in a GC parseable way.1727      // Specifically, these calls should be lowered to the1728      // __llvm_{memcpy|memmove}_element_unordered_atomic_safepoint symbols.1729      // Similarly to __llvm_deoptimize we want to resolve this now, since the1730      // verifier does not allow taking the address of an intrinsic function.1731      //1732      // Moreover we need to shuffle the arguments for the call in order to1733      // accommodate GC. The underlying source and destination objects might be1734      // relocated during copy operation should the GC occur. To relocate the1735      // derived source and destination pointers the implementation of the1736      // intrinsic should know the corresponding base pointers.1737      //1738      // To make the base pointers available pass them explicitly as arguments:1739      //   memcpy(dest_derived, source_derived, ...) =>1740      //   memcpy(dest_base, dest_offset, source_base, source_offset, ...)1741      auto &Context = Call->getContext();1742      auto &DL = Call->getDataLayout();1743      auto GetBaseAndOffset = [&](Value *Derived) {1744        Value *Base = nullptr;1745        // Optimizations in unreachable code might substitute the real pointer1746        // with undef, poison or null-derived constant. Return null base for1747        // them to be consistent with the handling in the main algorithm in1748        // findBaseDefiningValue.1749        if (isa<Constant>(Derived))1750          Base =1751              ConstantPointerNull::get(cast<PointerType>(Derived->getType()));1752        else {1753          assert(PointerToBase.count(Derived));1754          Base = PointerToBase.find(Derived)->second;1755        }1756        unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();1757        unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);1758        Value *Base_int = Builder.CreatePtrToInt(1759            Base, Type::getIntNTy(Context, IntPtrSize));1760        Value *Derived_int = Builder.CreatePtrToInt(1761            Derived, Type::getIntNTy(Context, IntPtrSize));1762        return std::make_pair(Base, Builder.CreateSub(Derived_int, Base_int));1763      };1764 1765      auto *Dest = CallArgs[0];1766      Value *DestBase, *DestOffset;1767      std::tie(DestBase, DestOffset) = GetBaseAndOffset(Dest);1768 1769      auto *Source = CallArgs[1];1770      Value *SourceBase, *SourceOffset;1771      std::tie(SourceBase, SourceOffset) = GetBaseAndOffset(Source);1772 1773      auto *LengthInBytes = CallArgs[2];1774      auto *ElementSizeCI = cast<ConstantInt>(CallArgs[3]);1775 1776      CallArgs.clear();1777      CallArgs.push_back(DestBase);1778      CallArgs.push_back(DestOffset);1779      CallArgs.push_back(SourceBase);1780      CallArgs.push_back(SourceOffset);1781      CallArgs.push_back(LengthInBytes);1782 1783      SmallVector<Type *, 8> DomainTy;1784      for (Value *Arg : CallArgs)1785        DomainTy.push_back(Arg->getType());1786      auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,1787                                    /* isVarArg = */ false);1788 1789      auto GetFunctionName = [](Intrinsic::ID IID, ConstantInt *ElementSizeCI) {1790        uint64_t ElementSize = ElementSizeCI->getZExtValue();1791        if (IID == Intrinsic::memcpy_element_unordered_atomic) {1792          switch (ElementSize) {1793          case 1:1794            return "__llvm_memcpy_element_unordered_atomic_safepoint_1";1795          case 2:1796            return "__llvm_memcpy_element_unordered_atomic_safepoint_2";1797          case 4:1798            return "__llvm_memcpy_element_unordered_atomic_safepoint_4";1799          case 8:1800            return "__llvm_memcpy_element_unordered_atomic_safepoint_8";1801          case 16:1802            return "__llvm_memcpy_element_unordered_atomic_safepoint_16";1803          default:1804            llvm_unreachable("unexpected element size!");1805          }1806        }1807        assert(IID == Intrinsic::memmove_element_unordered_atomic);1808        switch (ElementSize) {1809        case 1:1810          return "__llvm_memmove_element_unordered_atomic_safepoint_1";1811        case 2:1812          return "__llvm_memmove_element_unordered_atomic_safepoint_2";1813        case 4:1814          return "__llvm_memmove_element_unordered_atomic_safepoint_4";1815        case 8:1816          return "__llvm_memmove_element_unordered_atomic_safepoint_8";1817        case 16:1818          return "__llvm_memmove_element_unordered_atomic_safepoint_16";1819        default:1820          llvm_unreachable("unexpected element size!");1821        }1822      };1823 1824      CallTarget =1825          F->getParent()1826              ->getOrInsertFunction(GetFunctionName(IID, ElementSizeCI), FTy);1827    }1828  }1829 1830  // Create the statepoint given all the arguments1831  GCStatepointInst *Token = nullptr;1832  if (auto *CI = dyn_cast<CallInst>(Call)) {1833    CallInst *SPCall = Builder.CreateGCStatepointCall(1834        StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,1835        TransitionArgs, DeoptArgs, GCLive, "safepoint_token");1836 1837    SPCall->setTailCallKind(CI->getTailCallKind());1838    SPCall->setCallingConv(CI->getCallingConv());1839 1840    // Set up function attrs directly on statepoint and return attrs later for1841    // gc_result intrinsic.1842    SPCall->setAttributes(1843        legalizeCallAttributes(CI, IsMemIntrinsic, SPCall->getAttributes()));1844 1845    Token = cast<GCStatepointInst>(SPCall);1846 1847    // Put the following gc_result and gc_relocate calls immediately after the1848    // the old call (which we're about to delete)1849    assert(CI->getNextNode() && "Not a terminator, must have next!");1850    Builder.SetInsertPoint(CI->getNextNode());1851    Builder.SetCurrentDebugLocation(CI->getNextNode()->getDebugLoc());1852  } else {1853    auto *II = cast<InvokeInst>(Call);1854 1855    // Insert the new invoke into the old block.  We'll remove the old one in a1856    // moment at which point this will become the new terminator for the1857    // original block.1858    InvokeInst *SPInvoke = Builder.CreateGCStatepointInvoke(1859        StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(),1860        II->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs,1861        GCLive, "statepoint_token");1862 1863    SPInvoke->setCallingConv(II->getCallingConv());1864 1865    // Set up function attrs directly on statepoint and return attrs later for1866    // gc_result intrinsic.1867    SPInvoke->setAttributes(1868        legalizeCallAttributes(II, IsMemIntrinsic, SPInvoke->getAttributes()));1869 1870    Token = cast<GCStatepointInst>(SPInvoke);1871 1872    // Generate gc relocates in exceptional path1873    BasicBlock *UnwindBlock = II->getUnwindDest();1874    assert(!isa<PHINode>(UnwindBlock->begin()) &&1875           UnwindBlock->getUniquePredecessor() &&1876           "can't safely insert in this block!");1877 1878    Builder.SetInsertPoint(UnwindBlock, UnwindBlock->getFirstInsertionPt());1879    Builder.SetCurrentDebugLocation(II->getDebugLoc());1880 1881    // Attach exceptional gc relocates to the landingpad.1882    Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();1883    Result.UnwindToken = ExceptionalToken;1884 1885    CreateGCRelocates(LiveVariables, BasePtrs, ExceptionalToken, Builder, GC);1886 1887    // Generate gc relocates and returns for normal block1888    BasicBlock *NormalDest = II->getNormalDest();1889    assert(!isa<PHINode>(NormalDest->begin()) &&1890           NormalDest->getUniquePredecessor() &&1891           "can't safely insert in this block!");1892 1893    Builder.SetInsertPoint(NormalDest, NormalDest->getFirstInsertionPt());1894 1895    // gc relocates will be generated later as if it were regular call1896    // statepoint1897  }1898  assert(Token && "Should be set in one of the above branches!");1899 1900  if (IsDeoptimize) {1901    // If we're wrapping an @llvm.experimental.deoptimize in a statepoint, we1902    // transform the tail-call like structure to a call to a void function1903    // followed by unreachable to get better codegen.1904    Replacements.push_back(1905        DeferredReplacement::createDeoptimizeReplacement(Call));1906  } else {1907    Token->setName("statepoint_token");1908    if (!Call->getType()->isVoidTy() && !Call->use_empty()) {1909      StringRef Name = Call->hasName() ? Call->getName() : "";1910      CallInst *GCResult = Builder.CreateGCResult(Token, Call->getType(), Name);1911      GCResult->setAttributes(1912          AttributeList::get(GCResult->getContext(), AttributeList::ReturnIndex,1913                             Call->getAttributes().getRetAttrs()));1914 1915      // We cannot RAUW or delete CS.getInstruction() because it could be in the1916      // live set of some other safepoint, in which case that safepoint's1917      // PartiallyConstructedSafepointRecord will hold a raw pointer to this1918      // llvm::Instruction.  Instead, we defer the replacement and deletion to1919      // after the live sets have been made explicit in the IR, and we no longer1920      // have raw pointers to worry about.1921      Replacements.emplace_back(1922          DeferredReplacement::createRAUW(Call, GCResult));1923    } else {1924      Replacements.emplace_back(DeferredReplacement::createDelete(Call));1925    }1926  }1927 1928  Result.StatepointToken = Token;1929 1930  // Second, create a gc.relocate for every live variable1931  CreateGCRelocates(LiveVariables, BasePtrs, Token, Builder, GC);1932}1933 1934// Replace an existing gc.statepoint with a new one and a set of gc.relocates1935// which make the relocations happening at this safepoint explicit.1936//1937// WARNING: Does not do any fixup to adjust users of the original live1938// values.  That's the callers responsibility.1939static void1940makeStatepointExplicit(DominatorTree &DT, CallBase *Call,1941                       PartiallyConstructedSafepointRecord &Result,1942                       std::vector<DeferredReplacement> &Replacements,1943                       const PointerToBaseTy &PointerToBase, GCStrategy *GC) {1944  const auto &LiveSet = Result.LiveSet;1945 1946  // Convert to vector for efficient cross referencing.1947  SmallVector<Value *, 64> BaseVec, LiveVec;1948  LiveVec.reserve(LiveSet.size());1949  BaseVec.reserve(LiveSet.size());1950  for (Value *L : LiveSet) {1951    LiveVec.push_back(L);1952    assert(PointerToBase.count(L));1953    Value *Base = PointerToBase.find(L)->second;1954    BaseVec.push_back(Base);1955  }1956  assert(LiveVec.size() == BaseVec.size());1957 1958  // Do the actual rewriting and delete the old statepoint1959  makeStatepointExplicitImpl(Call, BaseVec, LiveVec, Result, Replacements,1960                             PointerToBase, GC);1961}1962 1963// Helper function for the relocationViaAlloca.1964//1965// It receives iterator to the statepoint gc relocates and emits a store to the1966// assigned location (via allocaMap) for the each one of them.  It adds the1967// visited values into the visitedLiveValues set, which we will later use them1968// for validation checking.1969static void1970insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs,1971                       DenseMap<Value *, AllocaInst *> &AllocaMap,1972                       DenseSet<Value *> &VisitedLiveValues) {1973  for (User *U : GCRelocs) {1974    GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U);1975    if (!Relocate)1976      continue;1977 1978    Value *OriginalValue = Relocate->getDerivedPtr();1979    assert(AllocaMap.count(OriginalValue));1980    Value *Alloca = AllocaMap[OriginalValue];1981 1982    // Emit store into the related alloca.1983    assert(Relocate->getNextNode() &&1984           "Should always have one since it's not a terminator");1985    new StoreInst(Relocate, Alloca, std::next(Relocate->getIterator()));1986 1987#ifndef NDEBUG1988    VisitedLiveValues.insert(OriginalValue);1989#endif1990  }1991}1992 1993// Helper function for the "relocationViaAlloca". Similar to the1994// "insertRelocationStores" but works for rematerialized values.1995static void insertRematerializationStores(1996    const RematerializedValueMapTy &RematerializedValues,1997    DenseMap<Value *, AllocaInst *> &AllocaMap,1998    DenseSet<Value *> &VisitedLiveValues) {1999  for (auto RematerializedValuePair: RematerializedValues) {2000    Instruction *RematerializedValue = RematerializedValuePair.first;2001    Value *OriginalValue = RematerializedValuePair.second;2002 2003    assert(AllocaMap.count(OriginalValue) &&2004           "Can not find alloca for rematerialized value");2005    Value *Alloca = AllocaMap[OriginalValue];2006 2007    new StoreInst(RematerializedValue, Alloca,2008                  std::next(RematerializedValue->getIterator()));2009 2010#ifndef NDEBUG2011    VisitedLiveValues.insert(OriginalValue);2012#endif2013  }2014}2015 2016/// Do all the relocation update via allocas and mem2reg2017static void relocationViaAlloca(2018    Function &F, DominatorTree &DT, ArrayRef<Value *> Live,2019    ArrayRef<PartiallyConstructedSafepointRecord> Records) {2020#ifndef NDEBUG2021  // record initial number of (static) allocas; we'll check we have the same2022  // number when we get done.2023  int InitialAllocaNum = 0;2024  for (Instruction &I : F.getEntryBlock())2025    if (isa<AllocaInst>(I))2026      InitialAllocaNum++;2027#endif2028 2029  // TODO-PERF: change data structures, reserve2030  DenseMap<Value *, AllocaInst *> AllocaMap;2031  SmallVector<AllocaInst *, 200> PromotableAllocas;2032  // Used later to chack that we have enough allocas to store all values2033  std::size_t NumRematerializedValues = 0;2034  PromotableAllocas.reserve(Live.size());2035 2036  // Emit alloca for "LiveValue" and record it in "allocaMap" and2037  // "PromotableAllocas"2038  const DataLayout &DL = F.getDataLayout();2039  auto emitAllocaFor = [&](Value *LiveValue) {2040    AllocaInst *Alloca =2041        new AllocaInst(LiveValue->getType(), DL.getAllocaAddrSpace(), "",2042                       F.getEntryBlock().getFirstNonPHIIt());2043    AllocaMap[LiveValue] = Alloca;2044    PromotableAllocas.push_back(Alloca);2045  };2046 2047  // Emit alloca for each live gc pointer2048  for (Value *V : Live)2049    emitAllocaFor(V);2050 2051  // Emit allocas for rematerialized values2052  for (const auto &Info : Records)2053    for (auto RematerializedValuePair : Info.RematerializedValues) {2054      Value *OriginalValue = RematerializedValuePair.second;2055      if (AllocaMap.contains(OriginalValue))2056        continue;2057 2058      emitAllocaFor(OriginalValue);2059      ++NumRematerializedValues;2060    }2061 2062  // The next two loops are part of the same conceptual operation.  We need to2063  // insert a store to the alloca after the original def and at each2064  // redefinition.  We need to insert a load before each use.  These are split2065  // into distinct loops for performance reasons.2066 2067  // Update gc pointer after each statepoint: either store a relocated value or2068  // null (if no relocated value was found for this gc pointer and it is not a2069  // gc_result).  This must happen before we update the statepoint with load of2070  // alloca otherwise we lose the link between statepoint and old def.2071  for (const auto &Info : Records) {2072    Value *Statepoint = Info.StatepointToken;2073 2074    // This will be used for consistency check2075    DenseSet<Value *> VisitedLiveValues;2076 2077    // Insert stores for normal statepoint gc relocates2078    insertRelocationStores(Statepoint->users(), AllocaMap, VisitedLiveValues);2079 2080    // In case if it was invoke statepoint2081    // we will insert stores for exceptional path gc relocates.2082    if (isa<InvokeInst>(Statepoint)) {2083      insertRelocationStores(Info.UnwindToken->users(), AllocaMap,2084                             VisitedLiveValues);2085    }2086 2087    // Do similar thing with rematerialized values2088    insertRematerializationStores(Info.RematerializedValues, AllocaMap,2089                                  VisitedLiveValues);2090 2091    if (ClobberNonLive) {2092      // As a debugging aid, pretend that an unrelocated pointer becomes null at2093      // the gc.statepoint.  This will turn some subtle GC problems into2094      // slightly easier to debug SEGVs.  Note that on large IR files with2095      // lots of gc.statepoints this is extremely costly both memory and time2096      // wise.2097      SmallVector<AllocaInst *, 64> ToClobber;2098      for (auto Pair : AllocaMap) {2099        Value *Def = Pair.first;2100        AllocaInst *Alloca = Pair.second;2101 2102        // This value was relocated2103        if (VisitedLiveValues.count(Def)) {2104          continue;2105        }2106        ToClobber.push_back(Alloca);2107      }2108 2109      auto InsertClobbersAt = [&](BasicBlock::iterator IP) {2110        for (auto *AI : ToClobber) {2111          auto AT = AI->getAllocatedType();2112          Constant *CPN;2113          if (AT->isVectorTy())2114            CPN = ConstantAggregateZero::get(AT);2115          else2116            CPN = ConstantPointerNull::get(cast<PointerType>(AT));2117          new StoreInst(CPN, AI, IP);2118        }2119      };2120 2121      // Insert the clobbering stores.  These may get intermixed with the2122      // gc.results and gc.relocates, but that's fine.2123      if (auto II = dyn_cast<InvokeInst>(Statepoint)) {2124        InsertClobbersAt(II->getNormalDest()->getFirstInsertionPt());2125        InsertClobbersAt(II->getUnwindDest()->getFirstInsertionPt());2126      } else {2127        InsertClobbersAt(2128            std::next(cast<Instruction>(Statepoint)->getIterator()));2129      }2130    }2131  }2132 2133  // Update use with load allocas and add store for gc_relocated.2134  for (auto Pair : AllocaMap) {2135    Value *Def = Pair.first;2136    AllocaInst *Alloca = Pair.second;2137 2138    // We pre-record the uses of allocas so that we dont have to worry about2139    // later update that changes the user information..2140 2141    SmallVector<Instruction *, 20> Uses;2142    // PERF: trade a linear scan for repeated reallocation2143    Uses.reserve(Def->getNumUses());2144    for (User *U : Def->users()) {2145      if (!isa<ConstantExpr>(U)) {2146        // If the def has a ConstantExpr use, then the def is either a2147        // ConstantExpr use itself or null.  In either case2148        // (recursively in the first, directly in the second), the oop2149        // it is ultimately dependent on is null and this particular2150        // use does not need to be fixed up.2151        Uses.push_back(cast<Instruction>(U));2152      }2153    }2154 2155    llvm::sort(Uses);2156    auto Last = llvm::unique(Uses);2157    Uses.erase(Last, Uses.end());2158 2159    for (Instruction *Use : Uses) {2160      if (isa<PHINode>(Use)) {2161        PHINode *Phi = cast<PHINode>(Use);2162        for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {2163          if (Def == Phi->getIncomingValue(i)) {2164            LoadInst *Load = new LoadInst(2165                Alloca->getAllocatedType(), Alloca, "",2166                Phi->getIncomingBlock(i)->getTerminator()->getIterator());2167            Phi->setIncomingValue(i, Load);2168          }2169        }2170      } else {2171        LoadInst *Load = new LoadInst(Alloca->getAllocatedType(), Alloca, "",2172                                      Use->getIterator());2173        Use->replaceUsesOfWith(Def, Load);2174      }2175    }2176 2177    // Emit store for the initial gc value.  Store must be inserted after load,2178    // otherwise store will be in alloca's use list and an extra load will be2179    // inserted before it.2180    StoreInst *Store = new StoreInst(Def, Alloca, /*volatile*/ false,2181                                     DL.getABITypeAlign(Def->getType()));2182    if (Instruction *Inst = dyn_cast<Instruction>(Def)) {2183      if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {2184        // InvokeInst is a terminator so the store need to be inserted into its2185        // normal destination block.2186        BasicBlock *NormalDest = Invoke->getNormalDest();2187        Store->insertBefore(NormalDest->getFirstNonPHIIt());2188      } else {2189        assert(!Inst->isTerminator() &&2190               "The only terminator that can produce a value is "2191               "InvokeInst which is handled above.");2192        Store->insertAfter(Inst->getIterator());2193      }2194    } else {2195      assert(isa<Argument>(Def));2196      Store->insertAfter(cast<Instruction>(Alloca)->getIterator());2197    }2198  }2199 2200  assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&2201         "we must have the same allocas with lives");2202  (void) NumRematerializedValues;2203  if (!PromotableAllocas.empty()) {2204    // Apply mem2reg to promote alloca to SSA2205    PromoteMemToReg(PromotableAllocas, DT);2206  }2207 2208#ifndef NDEBUG2209  for (auto &I : F.getEntryBlock())2210    if (isa<AllocaInst>(I))2211      InitialAllocaNum--;2212  assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas");2213#endif2214}2215 2216/// Insert holders so that each Value is obviously live through the entire2217/// lifetime of the call.2218static void insertUseHolderAfter(CallBase *Call, const ArrayRef<Value *> Values,2219                                 SmallVectorImpl<CallInst *> &Holders) {2220  if (Values.empty())2221    // No values to hold live, might as well not insert the empty holder2222    return;2223 2224  Module *M = Call->getModule();2225  // Use a dummy vararg function to actually hold the values live2226  FunctionCallee Func = M->getOrInsertFunction(2227      "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true));2228  if (isa<CallInst>(Call)) {2229    // For call safepoints insert dummy calls right after safepoint2230    Holders.push_back(2231        CallInst::Create(Func, Values, "", std::next(Call->getIterator())));2232    return;2233  }2234  // For invoke safepooints insert dummy calls both in normal and2235  // exceptional destination blocks2236  auto *II = cast<InvokeInst>(Call);2237  Holders.push_back(CallInst::Create(2238      Func, Values, "", II->getNormalDest()->getFirstInsertionPt()));2239  Holders.push_back(CallInst::Create(2240      Func, Values, "", II->getUnwindDest()->getFirstInsertionPt()));2241}2242 2243static void findLiveReferences(2244    Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,2245    MutableArrayRef<struct PartiallyConstructedSafepointRecord> records,2246    GCStrategy *GC) {2247  GCPtrLivenessData OriginalLivenessData;2248  computeLiveInValues(DT, F, OriginalLivenessData, GC);2249  for (size_t i = 0; i < records.size(); i++) {2250    struct PartiallyConstructedSafepointRecord &info = records[i];2251    analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info, GC);2252  }2253}2254 2255// Helper function for the "rematerializeLiveValues". It walks use chain2256// starting from the "CurrentValue" until it reaches the root of the chain, i.e.2257// the base or a value it cannot process. Only "simple" values are processed2258// (currently it is GEP's and casts). The returned root is  examined by the2259// callers of findRematerializableChainToBasePointer.  Fills "ChainToBase" array2260// with all visited values.2261static Value* findRematerializableChainToBasePointer(2262  SmallVectorImpl<Instruction*> &ChainToBase,2263  Value *CurrentValue) {2264  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {2265    ChainToBase.push_back(GEP);2266    return findRematerializableChainToBasePointer(ChainToBase,2267                                                  GEP->getPointerOperand());2268  }2269 2270  if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {2271    if (!CI->isNoopCast(CI->getDataLayout()))2272      return CI;2273 2274    ChainToBase.push_back(CI);2275    return findRematerializableChainToBasePointer(ChainToBase,2276                                                  CI->getOperand(0));2277  }2278 2279  // We have reached the root of the chain, which is either equal to the base or2280  // is the first unsupported value along the use chain.2281  return CurrentValue;2282}2283 2284// Helper function for the "rematerializeLiveValues". Compute cost of the use2285// chain we are going to rematerialize.2286static InstructionCost2287chainToBasePointerCost(SmallVectorImpl<Instruction *> &Chain,2288                       TargetTransformInfo &TTI) {2289  InstructionCost Cost = 0;2290 2291  for (Instruction *Instr : Chain) {2292    if (CastInst *CI = dyn_cast<CastInst>(Instr)) {2293      assert(CI->isNoopCast(CI->getDataLayout()) &&2294             "non noop cast is found during rematerialization");2295 2296      Type *SrcTy = CI->getOperand(0)->getType();2297      Cost += TTI.getCastInstrCost(CI->getOpcode(), CI->getType(), SrcTy,2298                                   TTI::getCastContextHint(CI),2299                                   TargetTransformInfo::TCK_SizeAndLatency, CI);2300 2301    } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) {2302      // Cost of the address calculation2303      Cost += TTI.getAddressComputationCost(2304          GEP->getType(), nullptr, nullptr,2305          TargetTransformInfo::TCK_SizeAndLatency);2306 2307      // And cost of the GEP itself2308      // TODO: Use TTI->getGEPCost here (it exists, but appears to be not2309      //       allowed for the external usage)2310      if (!GEP->hasAllConstantIndices())2311        Cost += 2;2312 2313    } else {2314      llvm_unreachable("unsupported instruction type during rematerialization");2315    }2316  }2317 2318  return Cost;2319}2320 2321static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi) {2322  unsigned PhiNum = OrigRootPhi.getNumIncomingValues();2323  if (PhiNum != AlternateRootPhi.getNumIncomingValues() ||2324      OrigRootPhi.getParent() != AlternateRootPhi.getParent())2325    return false;2326  // Map of incoming values and their corresponding basic blocks of2327  // OrigRootPhi.2328  SmallDenseMap<Value *, BasicBlock *, 8> CurrentIncomingValues;2329  for (unsigned i = 0; i < PhiNum; i++)2330    CurrentIncomingValues[OrigRootPhi.getIncomingValue(i)] =2331        OrigRootPhi.getIncomingBlock(i);2332 2333  // Both current and base PHIs should have same incoming values and2334  // the same basic blocks corresponding to the incoming values.2335  for (unsigned i = 0; i < PhiNum; i++) {2336    auto CIVI =2337        CurrentIncomingValues.find(AlternateRootPhi.getIncomingValue(i));2338    if (CIVI == CurrentIncomingValues.end())2339      return false;2340    BasicBlock *CurrentIncomingBB = CIVI->second;2341    if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i))2342      return false;2343  }2344  return true;2345}2346 2347// Find derived pointers that can be recomputed cheap enough and fill2348// RematerizationCandidates with such candidates.2349static void2350findRematerializationCandidates(PointerToBaseTy PointerToBase,2351                                RematCandTy &RematerizationCandidates,2352                                TargetTransformInfo &TTI) {2353  const unsigned int ChainLengthThreshold = 10;2354 2355  for (auto P2B : PointerToBase) {2356    auto *Derived = P2B.first;2357    auto *Base = P2B.second;2358    // Consider only derived pointers.2359    if (Derived == Base)2360      continue;2361 2362    // For each live pointer find its defining chain.2363    SmallVector<Instruction *, 3> ChainToBase;2364    Value *RootOfChain =2365        findRematerializableChainToBasePointer(ChainToBase, Derived);2366 2367    // Nothing to do, or chain is too long2368    if ( ChainToBase.size() == 0 ||2369        ChainToBase.size() > ChainLengthThreshold)2370      continue;2371 2372    // Handle the scenario where the RootOfChain is not equal to the2373    // Base Value, but they are essentially the same phi values.2374    if (Value *BaseVal = PointerToBase[Derived]; RootOfChain != BaseVal) {2375      PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);2376      PHINode *AlternateRootPhi = dyn_cast<PHINode>(BaseVal);2377      if (!OrigRootPhi || !AlternateRootPhi)2378        continue;2379      // PHI nodes that have the same incoming values, and belonging to the same2380      // basic blocks are essentially the same SSA value.  When the original phi2381      // has incoming values with different base pointers, the original phi is2382      // marked as conflict, and an additional `AlternateRootPhi` with the same2383      // incoming values get generated by the findBasePointer function. We need2384      // to identify the newly generated AlternateRootPhi (.base version of phi)2385      // and RootOfChain (the original phi node itself) are the same, so that we2386      // can rematerialize the gep and casts. This is a workaround for the2387      // deficiency in the findBasePointer algorithm.2388      if (!AreEquivalentPhiNodes(*OrigRootPhi, *AlternateRootPhi))2389        continue;2390    }2391    // Compute cost of this chain.2392    InstructionCost Cost = chainToBasePointerCost(ChainToBase, TTI);2393    // TODO: We can also account for cases when we will be able to remove some2394    //       of the rematerialized values by later optimization passes. I.e if2395    //       we rematerialized several intersecting chains. Or if original values2396    //       don't have any uses besides this statepoint.2397 2398    // Ok, there is a candidate.2399    RematerizlizationCandidateRecord Record;2400    Record.ChainToBase = ChainToBase;2401    Record.RootOfChain = RootOfChain;2402    Record.Cost = Cost;2403    RematerizationCandidates.insert({ Derived, Record });2404  }2405}2406 2407// Try to rematerialize derived pointers immediately before their uses2408// (instead of rematerializing after every statepoint it is live through).2409// This can be beneficial when derived pointer is live across many2410// statepoints, but uses are rare.2411static void rematerializeLiveValuesAtUses(2412    RematCandTy &RematerizationCandidates,2413    MutableArrayRef<PartiallyConstructedSafepointRecord> Records,2414    PointerToBaseTy &PointerToBase) {2415  if (!RematDerivedAtUses)2416    return;2417 2418  SmallVector<Instruction *, 32> LiveValuesToBeDeleted;2419 2420  LLVM_DEBUG(dbgs() << "Rematerialize derived pointers at uses, "2421                    << "Num statepoints: " << Records.size() << '\n');2422 2423  for (auto &It : RematerizationCandidates) {2424    Instruction *Cand = cast<Instruction>(It.first);2425    auto &Record = It.second;2426 2427    if (Record.Cost >= RematerializationThreshold)2428      continue;2429 2430    if (Cand->user_empty())2431      continue;2432 2433    if (Cand->hasOneUse())2434      if (auto *U = dyn_cast<Instruction>(Cand->getUniqueUndroppableUser()))2435        if (U->getParent() == Cand->getParent())2436          continue;2437 2438    // Rematerialization before PHI nodes is not implemented.2439    if (llvm::any_of(Cand->users(),2440                     [](const auto *U) { return isa<PHINode>(U); }))2441      continue;2442 2443    LLVM_DEBUG(dbgs() << "Trying cand " << *Cand << " ... ");2444 2445    // Count of rematerialization instructions we introduce is equal to number2446    // of candidate uses.2447    // Count of rematerialization instructions we eliminate is equal to number2448    // of statepoints it is live through.2449    // Consider transformation profitable if latter is greater than former2450    // (in other words, we create less than eliminate).2451    unsigned NumLiveStatepoints = llvm::count_if(2452        Records, [Cand](const auto &R) { return R.LiveSet.contains(Cand); });2453    unsigned NumUses = Cand->getNumUses();2454 2455    LLVM_DEBUG(dbgs() << "Num uses: " << NumUses << " Num live statepoints: "2456                      << NumLiveStatepoints << " ");2457 2458    if (NumLiveStatepoints < NumUses) {2459      LLVM_DEBUG(dbgs() << "not profitable\n");2460      continue;2461    }2462 2463    // If rematerialization is 'free', then favor rematerialization at2464    // uses as it generally shortens live ranges.2465    // TODO: Short (size ==1) chains only?2466    if (NumLiveStatepoints == NumUses && Record.Cost > 0) {2467      LLVM_DEBUG(dbgs() << "not profitable\n");2468      continue;2469    }2470 2471    LLVM_DEBUG(dbgs() << "looks profitable\n");2472 2473    // ChainToBase may contain another remat candidate (as a sub chain) which2474    // has been rewritten by now. Need to recollect chain to have up to date2475    // value.2476    // TODO: sort records in findRematerializationCandidates() in2477    // decreasing chain size order?2478    if (Record.ChainToBase.size() > 1) {2479      Record.ChainToBase.clear();2480      findRematerializableChainToBasePointer(Record.ChainToBase, Cand);2481    }2482 2483    // Current rematerialization algorithm is very simple: we rematerialize2484    // immediately before EVERY use, even if there are several uses in same2485    // block or if use is local to Cand Def. The reason is that this allows2486    // us to avoid recomputing liveness without complicated analysis:2487    // - If we did not eliminate all uses of original Candidate, we do not2488    //   know exaclty in what BBs it is still live.2489    // - If we rematerialize once per BB, we need to find proper insertion2490    //   place (first use in block, but after Def) and analyze if there is2491    //   statepoint between uses in the block.2492    while (!Cand->user_empty()) {2493      Instruction *UserI = cast<Instruction>(*Cand->user_begin());2494      Instruction *RematChain =2495          rematerializeChain(Record.ChainToBase, UserI->getIterator(),2496                             Record.RootOfChain, PointerToBase[Cand]);2497      UserI->replaceUsesOfWith(Cand, RematChain);2498      PointerToBase[RematChain] = PointerToBase[Cand];2499    }2500    LiveValuesToBeDeleted.push_back(Cand);2501  }2502 2503  LLVM_DEBUG(dbgs() << "Rematerialized " << LiveValuesToBeDeleted.size()2504                    << " derived pointers\n");2505  for (auto *Cand : LiveValuesToBeDeleted) {2506    assert(Cand->use_empty() && "Unexpected user remain");2507    RematerizationCandidates.erase(Cand);2508    for (auto &R : Records) {2509      assert(!R.LiveSet.contains(Cand) ||2510             R.LiveSet.contains(PointerToBase[Cand]));2511      R.LiveSet.remove(Cand);2512    }2513  }2514 2515  // Recollect not rematerialized chains - we might have rewritten2516  // their sub-chains.2517  if (!LiveValuesToBeDeleted.empty()) {2518    for (auto &P : RematerizationCandidates) {2519      auto &R = P.second;2520      if (R.ChainToBase.size() > 1) {2521        R.ChainToBase.clear();2522        findRematerializableChainToBasePointer(R.ChainToBase, P.first);2523      }2524    }2525  }2526}2527 2528// From the statepoint live set pick values that are cheaper to recompute then2529// to relocate. Remove this values from the live set, rematerialize them after2530// statepoint and record them in "Info" structure. Note that similar to2531// relocated values we don't do any user adjustments here.2532static void rematerializeLiveValues(CallBase *Call,2533                                    PartiallyConstructedSafepointRecord &Info,2534                                    PointerToBaseTy &PointerToBase,2535                                    RematCandTy &RematerizationCandidates,2536                                    TargetTransformInfo &TTI) {2537  // Record values we are going to delete from this statepoint live set.2538  // We can not di this in following loop due to iterator invalidation.2539  SmallVector<Value *, 32> LiveValuesToBeDeleted;2540 2541  for (Value *LiveValue : Info.LiveSet) {2542    auto It = RematerizationCandidates.find(LiveValue);2543    if (It == RematerizationCandidates.end())2544      continue;2545 2546    RematerizlizationCandidateRecord &Record = It->second;2547 2548    InstructionCost Cost = Record.Cost;2549    // For invokes we need to rematerialize each chain twice - for normal and2550    // for unwind basic blocks. Model this by multiplying cost by two.2551    if (isa<InvokeInst>(Call))2552      Cost *= 2;2553 2554    // If it's too expensive - skip it.2555    if (Cost >= RematerializationThreshold)2556      continue;2557 2558    // Remove value from the live set2559    LiveValuesToBeDeleted.push_back(LiveValue);2560 2561    // Clone instructions and record them inside "Info" structure.2562 2563    // Different cases for calls and invokes. For invokes we need to clone2564    // instructions both on normal and unwind path.2565    if (isa<CallInst>(Call)) {2566      Instruction *InsertBefore = Call->getNextNode();2567      assert(InsertBefore);2568      Instruction *RematerializedValue =2569          rematerializeChain(Record.ChainToBase, InsertBefore->getIterator(),2570                             Record.RootOfChain, PointerToBase[LiveValue]);2571      Info.RematerializedValues[RematerializedValue] = LiveValue;2572    } else {2573      auto *Invoke = cast<InvokeInst>(Call);2574 2575      BasicBlock::iterator NormalInsertBefore =2576          Invoke->getNormalDest()->getFirstInsertionPt();2577      BasicBlock::iterator UnwindInsertBefore =2578          Invoke->getUnwindDest()->getFirstInsertionPt();2579 2580      Instruction *NormalRematerializedValue =2581          rematerializeChain(Record.ChainToBase, NormalInsertBefore,2582                             Record.RootOfChain, PointerToBase[LiveValue]);2583      Instruction *UnwindRematerializedValue =2584          rematerializeChain(Record.ChainToBase, UnwindInsertBefore,2585                             Record.RootOfChain, PointerToBase[LiveValue]);2586 2587      Info.RematerializedValues[NormalRematerializedValue] = LiveValue;2588      Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;2589    }2590  }2591 2592  // Remove rematerialized values from the live set.2593  for (auto *LiveValue: LiveValuesToBeDeleted) {2594    Info.LiveSet.remove(LiveValue);2595  }2596}2597 2598static bool inlineGetBaseAndOffset(Function &F,2599                                   SmallVectorImpl<CallInst *> &Intrinsics,2600                                   DefiningValueMapTy &DVCache,2601                                   IsKnownBaseMapTy &KnownBases) {2602  auto &Context = F.getContext();2603  auto &DL = F.getDataLayout();2604  bool Changed = false;2605 2606  for (auto *Callsite : Intrinsics)2607    switch (Callsite->getIntrinsicID()) {2608    case Intrinsic::experimental_gc_get_pointer_base: {2609      Changed = true;2610      Value *Base =2611          findBasePointer(Callsite->getOperand(0), DVCache, KnownBases);2612      assert(!DVCache.count(Callsite));2613      Callsite->replaceAllUsesWith(Base);2614      if (!Base->hasName())2615        Base->takeName(Callsite);2616      Callsite->eraseFromParent();2617      break;2618    }2619    case Intrinsic::experimental_gc_get_pointer_offset: {2620      Changed = true;2621      Value *Derived = Callsite->getOperand(0);2622      Value *Base = findBasePointer(Derived, DVCache, KnownBases);2623      assert(!DVCache.count(Callsite));2624      unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();2625      unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);2626      IRBuilder<> Builder(Callsite);2627      Value *BaseInt =2628          Builder.CreatePtrToInt(Base, Type::getIntNTy(Context, IntPtrSize),2629                                 suffixed_name_or(Base, ".int", ""));2630      Value *DerivedInt =2631          Builder.CreatePtrToInt(Derived, Type::getIntNTy(Context, IntPtrSize),2632                                 suffixed_name_or(Derived, ".int", ""));2633      Value *Offset = Builder.CreateSub(DerivedInt, BaseInt);2634      Callsite->replaceAllUsesWith(Offset);2635      Offset->takeName(Callsite);2636      Callsite->eraseFromParent();2637      break;2638    }2639    default:2640      llvm_unreachable("Unknown intrinsic");2641    }2642 2643  return Changed;2644}2645 2646static bool insertParsePoints(Function &F, DominatorTree &DT,2647                              TargetTransformInfo &TTI,2648                              SmallVectorImpl<CallBase *> &ToUpdate,2649                              DefiningValueMapTy &DVCache,2650                              IsKnownBaseMapTy &KnownBases) {2651  std::unique_ptr<GCStrategy> GC = findGCStrategy(F);2652 2653#ifndef NDEBUG2654  // Validate the input2655  std::set<CallBase *> Uniqued;2656  Uniqued.insert(ToUpdate.begin(), ToUpdate.end());2657  assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");2658 2659  for (CallBase *Call : ToUpdate)2660    assert(Call->getFunction() == &F);2661#endif2662 2663  // When inserting gc.relocates for invokes, we need to be able to insert at2664  // the top of the successor blocks.  See the comment on2665  // normalForInvokeSafepoint on exactly what is needed.  Note that this step2666  // may restructure the CFG.2667  for (CallBase *Call : ToUpdate) {2668    auto *II = dyn_cast<InvokeInst>(Call);2669    if (!II)2670      continue;2671    normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);2672    normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);2673  }2674 2675  // A list of dummy calls added to the IR to keep various values obviously2676  // live in the IR.  We'll remove all of these when done.2677  SmallVector<CallInst *, 64> Holders;2678 2679  // Insert a dummy call with all of the deopt operands we'll need for the2680  // actual safepoint insertion as arguments.  This ensures reference operands2681  // in the deopt argument list are considered live through the safepoint (and2682  // thus makes sure they get relocated.)2683  for (CallBase *Call : ToUpdate) {2684    SmallVector<Value *, 64> DeoptValues;2685 2686    for (Value *Arg : GetDeoptBundleOperands(Call)) {2687      assert(!isUnhandledGCPointerType(Arg->getType(), GC.get()) &&2688             "support for FCA unimplemented");2689      if (isHandledGCPointerType(Arg->getType(), GC.get()))2690        DeoptValues.push_back(Arg);2691    }2692 2693    insertUseHolderAfter(Call, DeoptValues, Holders);2694  }2695 2696  SmallVector<PartiallyConstructedSafepointRecord, 64> Records(ToUpdate.size());2697 2698  // A) Identify all gc pointers which are statically live at the given call2699  // site.2700  findLiveReferences(F, DT, ToUpdate, Records, GC.get());2701 2702  /// Global mapping from live pointers to a base-defining-value.2703  PointerToBaseTy PointerToBase;2704 2705  // B) Find the base pointers for each live pointer2706  for (size_t i = 0; i < Records.size(); i++) {2707    PartiallyConstructedSafepointRecord &info = Records[i];2708    findBasePointers(DT, DVCache, ToUpdate[i], info, PointerToBase, KnownBases);2709  }2710  if (PrintBasePointers) {2711    errs() << "Base Pairs (w/o Relocation):\n";2712    for (auto &Pair : PointerToBase) {2713      errs() << " derived ";2714      Pair.first->printAsOperand(errs(), false);2715      errs() << " base ";2716      Pair.second->printAsOperand(errs(), false);2717      errs() << "\n";2718      ;2719    }2720  }2721 2722  // The base phi insertion logic (for any safepoint) may have inserted new2723  // instructions which are now live at some safepoint.  The simplest such2724  // example is:2725  // loop:2726  //   phi a  <-- will be a new base_phi here2727  //   safepoint 1 <-- that needs to be live here2728  //   gep a + 12729  //   safepoint 22730  //   br loop2731  // We insert some dummy calls after each safepoint to definitely hold live2732  // the base pointers which were identified for that safepoint.  We'll then2733  // ask liveness for _every_ base inserted to see what is now live.  Then we2734  // remove the dummy calls.2735  Holders.reserve(Holders.size() + Records.size());2736  for (size_t i = 0; i < Records.size(); i++) {2737    PartiallyConstructedSafepointRecord &Info = Records[i];2738 2739    SmallVector<Value *, 128> Bases;2740    for (auto *Derived : Info.LiveSet) {2741      assert(PointerToBase.count(Derived) && "Missed base for derived pointer");2742      Bases.push_back(PointerToBase[Derived]);2743    }2744 2745    insertUseHolderAfter(ToUpdate[i], Bases, Holders);2746  }2747 2748  // By selecting base pointers, we've effectively inserted new uses. Thus, we2749  // need to rerun liveness.  We may *also* have inserted new defs, but that's2750  // not the key issue.2751  recomputeLiveInValues(F, DT, ToUpdate, Records, PointerToBase, GC.get());2752 2753  if (PrintBasePointers) {2754    errs() << "Base Pairs: (w/Relocation)\n";2755    for (auto Pair : PointerToBase) {2756      errs() << " derived ";2757      Pair.first->printAsOperand(errs(), false);2758      errs() << " base ";2759      Pair.second->printAsOperand(errs(), false);2760      errs() << "\n";2761    }2762  }2763 2764  // It is possible that non-constant live variables have a constant base.  For2765  // example, a GEP with a variable offset from a global.  In this case we can2766  // remove it from the liveset.  We already don't add constants to the liveset2767  // because we assume they won't move at runtime and the GC doesn't need to be2768  // informed about them.  The same reasoning applies if the base is constant.2769  // Note that the relocation placement code relies on this filtering for2770  // correctness as it expects the base to be in the liveset, which isn't true2771  // if the base is constant.2772  for (auto &Info : Records) {2773    Info.LiveSet.remove_if([&](Value *LiveV) {2774      assert(PointerToBase.count(LiveV) && "Missed base for derived pointer");2775      return isa<Constant>(PointerToBase[LiveV]);2776    });2777  }2778 2779  for (CallInst *CI : Holders)2780    CI->eraseFromParent();2781 2782  Holders.clear();2783 2784  // Compute the cost of possible re-materialization of derived pointers.2785  RematCandTy RematerizationCandidates;2786  findRematerializationCandidates(PointerToBase, RematerizationCandidates, TTI);2787 2788  // In order to reduce live set of statepoint we might choose to rematerialize2789  // some values instead of relocating them. This is purely an optimization and2790  // does not influence correctness.2791  // First try rematerialization at uses, then after statepoints.2792  rematerializeLiveValuesAtUses(RematerizationCandidates, Records,2793                                PointerToBase);2794  for (size_t i = 0; i < Records.size(); i++)2795    rematerializeLiveValues(ToUpdate[i], Records[i], PointerToBase,2796                            RematerizationCandidates, TTI);2797 2798  // We need this to safely RAUW and delete call or invoke return values that2799  // may themselves be live over a statepoint.  For details, please see usage in2800  // makeStatepointExplicitImpl.2801  std::vector<DeferredReplacement> Replacements;2802 2803  // Now run through and replace the existing statepoints with new ones with2804  // the live variables listed.  We do not yet update uses of the values being2805  // relocated. We have references to live variables that need to2806  // survive to the last iteration of this loop.  (By construction, the2807  // previous statepoint can not be a live variable, thus we can and remove2808  // the old statepoint calls as we go.)2809  for (size_t i = 0; i < Records.size(); i++)2810    makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements,2811                           PointerToBase, GC.get());2812 2813  ToUpdate.clear(); // prevent accident use of invalid calls.2814 2815  for (auto &PR : Replacements)2816    PR.doReplacement();2817 2818  Replacements.clear();2819 2820  for (auto &Info : Records) {2821    // These live sets may contain state Value pointers, since we replaced calls2822    // with operand bundles with calls wrapped in gc.statepoint, and some of2823    // those calls may have been def'ing live gc pointers.  Clear these out to2824    // avoid accidentally using them.2825    //2826    // TODO: We should create a separate data structure that does not contain2827    // these live sets, and migrate to using that data structure from this point2828    // onward.2829    Info.LiveSet.clear();2830  }2831  PointerToBase.clear();2832 2833  // Do all the fixups of the original live variables to their relocated selves.2834  // A SmallSetVector is used to collect live variables while retaining the2835  // order in which we add them, which is important for reproducible tests.2836  SmallSetVector<Value *, 16> Live;2837  for (const PartiallyConstructedSafepointRecord &Info : Records) {2838    // We can't simply save the live set from the original insertion.  One of2839    // the live values might be the result of a call which needs a safepoint.2840    // That Value* no longer exists and we need to use the new gc_result.2841    // Thankfully, the live set is embedded in the statepoint (and updated), so2842    // we just grab that.2843    Live.insert_range(Info.StatepointToken->gc_live());2844#ifndef NDEBUG2845    // Do some basic validation checking on our liveness results before2846    // performing relocation.  Relocation can and will turn mistakes in liveness2847    // results into non-sensical code which is must harder to debug.2848    // TODO: It would be nice to test consistency as well2849    assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) &&2850           "statepoint must be reachable or liveness is meaningless");2851    for (Value *V : Info.StatepointToken->gc_live()) {2852      if (!isa<Instruction>(V))2853        // Non-instruction values trivial dominate all possible uses2854        continue;2855      auto *LiveInst = cast<Instruction>(V);2856      assert(DT.isReachableFromEntry(LiveInst->getParent()) &&2857             "unreachable values should never be live");2858      assert(DT.dominates(LiveInst, Info.StatepointToken) &&2859             "basic SSA liveness expectation violated by liveness analysis");2860    }2861#endif2862  }2863 2864#ifndef NDEBUG2865  // Validation check2866  for (auto *Ptr : Live)2867    assert(isHandledGCPointerType(Ptr->getType(), GC.get()) &&2868           "must be a gc pointer type");2869#endif2870 2871  relocationViaAlloca(F, DT, Live.getArrayRef(), Records);2872  return !Records.empty();2873}2874 2875// List of all parameter and return attributes which must be stripped when2876// lowering from the abstract machine model.  Note that we list attributes2877// here which aren't valid as return attributes, that is okay.2878static AttributeMask getParamAndReturnAttributesToRemove() {2879  AttributeMask R;2880  R.addAttribute(Attribute::Dereferenceable);2881  R.addAttribute(Attribute::DereferenceableOrNull);2882  R.addAttribute(Attribute::ReadNone);2883  R.addAttribute(Attribute::ReadOnly);2884  R.addAttribute(Attribute::WriteOnly);2885  R.addAttribute(Attribute::NoAlias);2886  R.addAttribute(Attribute::NoFree);2887  return R;2888}2889 2890static void stripNonValidAttributesFromPrototype(Function &F) {2891  LLVMContext &Ctx = F.getContext();2892 2893  // Intrinsics are very delicate.  Lowering sometimes depends the presence2894  // of certain attributes for correctness, but we may have also inferred2895  // additional ones in the abstract machine model which need stripped.  This2896  // assumes that the attributes defined in Intrinsic.td are conservatively2897  // correct for both physical and abstract model.2898  if (Intrinsic::ID id = F.getIntrinsicID()) {2899    F.setAttributes(Intrinsic::getAttributes(Ctx, id, F.getFunctionType()));2900    return;2901  }2902 2903  AttributeMask R = getParamAndReturnAttributesToRemove();2904  for (Argument &A : F.args())2905    if (isa<PointerType>(A.getType()))2906      F.removeParamAttrs(A.getArgNo(), R);2907 2908  if (isa<PointerType>(F.getReturnType()))2909    F.removeRetAttrs(R);2910 2911  for (auto Attr : FnAttrsToStrip)2912    F.removeFnAttr(Attr);2913}2914 2915/// Certain metadata on instructions are invalid after running RS4GC.2916/// Optimizations that run after RS4GC can incorrectly use this metadata to2917/// optimize functions. We drop such metadata on the instruction.2918static void stripInvalidMetadataFromInstruction(Instruction &I) {2919  if (!isa<LoadInst>(I) && !isa<StoreInst>(I))2920    return;2921  // These are the attributes that are still valid on loads and stores after2922  // RS4GC.2923  // The metadata implying dereferenceability and noalias are (conservatively)2924  // dropped.  This is because semantically, after RewriteStatepointsForGC runs,2925  // all calls to gc.statepoint "free" the entire heap. Also, gc.statepoint can2926  // touch the entire heap including noalias objects. Note: The reasoning is2927  // same as stripping the dereferenceability and noalias attributes that are2928  // analogous to the metadata counterparts.2929  // We also drop the invariant.load metadata on the load because that metadata2930  // implies the address operand to the load points to memory that is never2931  // changed once it became dereferenceable. This is no longer true after RS4GC.2932  // Similar reasoning applies to invariant.group metadata, which applies to2933  // loads within a group.2934  unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,2935                         LLVMContext::MD_range,2936                         LLVMContext::MD_alias_scope,2937                         LLVMContext::MD_nontemporal,2938                         LLVMContext::MD_nonnull,2939                         LLVMContext::MD_align,2940                         LLVMContext::MD_type};2941 2942  // Drops all metadata on the instruction other than ValidMetadataAfterRS4GC.2943  I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);2944}2945 2946static void stripNonValidDataFromBody(Function &F) {2947  if (F.empty())2948    return;2949 2950  LLVMContext &Ctx = F.getContext();2951  MDBuilder Builder(Ctx);2952 2953  // Set of invariantstart instructions that we need to remove.2954  // Use this to avoid invalidating the instruction iterator.2955  SmallVector<IntrinsicInst*, 12> InvariantStartInstructions;2956 2957  for (Instruction &I : instructions(F)) {2958    // invariant.start on memory location implies that the referenced memory2959    // location is constant and unchanging. This is no longer true after2960    // RewriteStatepointsForGC runs because there can be calls to gc.statepoint2961    // which frees the entire heap and the presence of invariant.start allows2962    // the optimizer to sink the load of a memory location past a statepoint,2963    // which is incorrect.2964    if (auto *II = dyn_cast<IntrinsicInst>(&I))2965      if (II->getIntrinsicID() == Intrinsic::invariant_start) {2966        InvariantStartInstructions.push_back(II);2967        continue;2968      }2969 2970    if (MDNode *Tag = I.getMetadata(LLVMContext::MD_tbaa)) {2971      MDNode *MutableTBAA = Builder.createMutableTBAAAccessTag(Tag);2972      I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);2973    }2974 2975    stripInvalidMetadataFromInstruction(I);2976 2977    AttributeMask R = getParamAndReturnAttributesToRemove();2978    if (auto *Call = dyn_cast<CallBase>(&I)) {2979      for (int i = 0, e = Call->arg_size(); i != e; i++)2980        if (isa<PointerType>(Call->getArgOperand(i)->getType()))2981          Call->removeParamAttrs(i, R);2982      if (isa<PointerType>(Call->getType()))2983        Call->removeRetAttrs(R);2984    }2985  }2986 2987  // Delete the invariant.start instructions and RAUW poison.2988  for (auto *II : InvariantStartInstructions) {2989    II->replaceAllUsesWith(PoisonValue::get(II->getType()));2990    II->eraseFromParent();2991  }2992}2993 2994/// Looks up the GC strategy for a given function, returning null if the2995/// function doesn't have a GC tag. The strategy is stored in the cache.2996static std::unique_ptr<GCStrategy> findGCStrategy(Function &F) {2997  if (!F.hasGC())2998    return nullptr;2999 3000  return getGCStrategy(F.getGC());3001}3002 3003/// Returns true if this function should be rewritten by this pass.  The main3004/// point of this function is as an extension point for custom logic.3005static bool shouldRewriteStatepointsIn(Function &F) {3006  if (!F.hasGC())3007    return false;3008 3009  std::unique_ptr<GCStrategy> Strategy = findGCStrategy(F);3010 3011  assert(Strategy && "GC strategy is required by function, but was not found");3012 3013  return Strategy->useRS4GC();3014}3015 3016static void stripNonValidData(Module &M) {3017#ifndef NDEBUG3018  assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!");3019#endif3020 3021  for (Function &F : M)3022    stripNonValidAttributesFromPrototype(F);3023 3024  for (Function &F : M)3025    stripNonValidDataFromBody(F);3026}3027 3028bool RewriteStatepointsForGC::runOnFunction(Function &F, DominatorTree &DT,3029                                            TargetTransformInfo &TTI,3030                                            const TargetLibraryInfo &TLI) {3031  assert(!F.isDeclaration() && !F.empty() &&3032         "need function body to rewrite statepoints in");3033  assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision");3034 3035  auto NeedsRewrite = [&TLI](Instruction &I) {3036    if (const auto *Call = dyn_cast<CallBase>(&I)) {3037      if (isa<GCStatepointInst>(Call))3038        return false;3039      if (callsGCLeafFunction(Call, TLI))3040        return false;3041 3042      // Normally it's up to the frontend to make sure that non-leaf calls also3043      // have proper deopt state if it is required. We make an exception for3044      // element atomic memcpy/memmove intrinsics here. Unlike other intrinsics3045      // these are non-leaf by default. They might be generated by the optimizer3046      // which doesn't know how to produce a proper deopt state. So if we see a3047      // non-leaf memcpy/memmove without deopt state just treat it as a leaf3048      // copy and don't produce a statepoint.3049      if (!AllowStatepointWithNoDeoptInfo && !Call->hasDeoptState()) {3050        assert(isa<AnyMemTransferInst>(Call) &&3051               cast<AnyMemTransferInst>(Call)->isAtomic() &&3052               "Don't expect any other calls here!");3053        return false;3054      }3055      return true;3056    }3057    return false;3058  };3059 3060  // Delete any unreachable statepoints so that we don't have unrewritten3061  // statepoints surviving this pass.  This makes testing easier and the3062  // resulting IR less confusing to human readers.3063  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);3064  bool MadeChange = removeUnreachableBlocks(F, &DTU);3065  // Flush the Dominator Tree.3066  DTU.getDomTree();3067 3068  // Gather all the statepoints which need rewritten.  Be careful to only3069  // consider those in reachable code since we need to ask dominance queries3070  // when rewriting.  We'll delete the unreachable ones in a moment.3071  SmallVector<CallBase *, 64> ParsePointNeeded;3072  SmallVector<CallInst *, 64> Intrinsics;3073  for (Instruction &I : instructions(F)) {3074    // TODO: only the ones with the flag set!3075    if (NeedsRewrite(I)) {3076      // NOTE removeUnreachableBlocks() is stronger than3077      // DominatorTree::isReachableFromEntry(). In other words3078      // removeUnreachableBlocks can remove some blocks for which3079      // isReachableFromEntry() returns true.3080      assert(DT.isReachableFromEntry(I.getParent()) &&3081            "no unreachable blocks expected");3082      ParsePointNeeded.push_back(cast<CallBase>(&I));3083    }3084    if (auto *CI = dyn_cast<CallInst>(&I))3085      if (CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_base ||3086          CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_offset)3087        Intrinsics.emplace_back(CI);3088  }3089 3090  // Return early if no work to do.3091  if (ParsePointNeeded.empty() && Intrinsics.empty())3092    return MadeChange;3093 3094  // As a prepass, go ahead and aggressively destroy single entry phi nodes.3095  // These are created by LCSSA.  They have the effect of increasing the size3096  // of liveness sets for no good reason.  It may be harder to do this post3097  // insertion since relocations and base phis can confuse things.3098  for (BasicBlock &BB : F)3099    if (BB.getUniquePredecessor())3100      MadeChange |= FoldSingleEntryPHINodes(&BB);3101 3102  // Before we start introducing relocations, we want to tweak the IR a bit to3103  // avoid unfortunate code generation effects.  The main example is that we3104  // want to try to make sure the comparison feeding a branch is after any3105  // safepoints.  Otherwise, we end up with a comparison of pre-relocation3106  // values feeding a branch after relocation.  This is semantically correct,3107  // but results in extra register pressure since both the pre-relocation and3108  // post-relocation copies must be available in registers.  For code without3109  // relocations this is handled elsewhere, but teaching the scheduler to3110  // reverse the transform we're about to do would be slightly complex.3111  // Note: This may extend the live range of the inputs to the icmp and thus3112  // increase the liveset of any statepoint we move over.  This is profitable3113  // as long as all statepoints are in rare blocks.  If we had in-register3114  // lowering for live values this would be a much safer transform.3115  auto getConditionInst = [](Instruction *TI) -> Instruction * {3116    if (auto *BI = dyn_cast<BranchInst>(TI))3117      if (BI->isConditional())3118        return dyn_cast<Instruction>(BI->getCondition());3119    // TODO: Extend this to handle switches3120    return nullptr;3121  };3122  for (BasicBlock &BB : F) {3123    Instruction *TI = BB.getTerminator();3124    if (auto *Cond = getConditionInst(TI))3125      // TODO: Handle more than just ICmps here.  We should be able to move3126      // most instructions without side effects or memory access.3127      if (isa<ICmpInst>(Cond) && Cond->hasOneUse()) {3128        MadeChange = true;3129        Cond->moveBefore(TI->getIterator());3130      }3131  }3132 3133  // Nasty workaround - The base computation code in the main algorithm doesn't3134  // consider the fact that a GEP can be used to convert a scalar to a vector.3135  // The right fix for this is to integrate GEPs into the base rewriting3136  // algorithm properly, this is just a short term workaround to prevent3137  // crashes by canonicalizing such GEPs into fully vector GEPs.3138  for (Instruction &I : instructions(F)) {3139    if (!isa<GetElementPtrInst>(I))3140      continue;3141 3142    unsigned VF = 0;3143    for (unsigned i = 0; i < I.getNumOperands(); i++)3144      if (auto *OpndVTy = dyn_cast<VectorType>(I.getOperand(i)->getType())) {3145        assert(VF == 0 ||3146               VF == cast<FixedVectorType>(OpndVTy)->getNumElements());3147        VF = cast<FixedVectorType>(OpndVTy)->getNumElements();3148      }3149 3150    // It's the vector to scalar traversal through the pointer operand which3151    // confuses base pointer rewriting, so limit ourselves to that case.3152    if (!I.getOperand(0)->getType()->isVectorTy() && VF != 0) {3153      IRBuilder<> B(&I);3154      auto *Splat = B.CreateVectorSplat(VF, I.getOperand(0));3155      I.setOperand(0, Splat);3156      MadeChange = true;3157    }3158  }3159 3160  // Cache the 'defining value' relation used in the computation and3161  // insertion of base phis and selects.  This ensures that we don't insert3162  // large numbers of duplicate base_phis. Use one cache for both3163  // inlineGetBaseAndOffset() and insertParsePoints().3164  DefiningValueMapTy DVCache;3165 3166  // Mapping between a base values and a flag indicating whether it's a known3167  // base or not.3168  IsKnownBaseMapTy KnownBases;3169 3170  if (!Intrinsics.empty())3171    // Inline @gc.get.pointer.base() and @gc.get.pointer.offset() before finding3172    // live references.3173    MadeChange |= inlineGetBaseAndOffset(F, Intrinsics, DVCache, KnownBases);3174 3175  if (!ParsePointNeeded.empty())3176    MadeChange |=3177        insertParsePoints(F, DT, TTI, ParsePointNeeded, DVCache, KnownBases);3178 3179  return MadeChange;3180}3181 3182// liveness computation via standard dataflow3183// -------------------------------------------------------------------3184 3185// TODO: Consider using bitvectors for liveness, the set of potentially3186// interesting values should be small and easy to pre-compute.3187 3188/// Compute the live-in set for the location rbegin starting from3189/// the live-out set of the basic block3190static void computeLiveInValues(BasicBlock::reverse_iterator Begin,3191                                BasicBlock::reverse_iterator End,3192                                SetVector<Value *> &LiveTmp, GCStrategy *GC) {3193  for (auto &I : make_range(Begin, End)) {3194    // KILL/Def - Remove this definition from LiveIn3195    LiveTmp.remove(&I);3196 3197    // Don't consider *uses* in PHI nodes, we handle their contribution to3198    // predecessor blocks when we seed the LiveOut sets3199    if (isa<PHINode>(I))3200      continue;3201 3202    // USE - Add to the LiveIn set for this instruction3203    for (Value *V : I.operands()) {3204      assert(!isUnhandledGCPointerType(V->getType(), GC) &&3205             "support for FCA unimplemented");3206      if (isHandledGCPointerType(V->getType(), GC) && !isa<Constant>(V)) {3207        // The choice to exclude all things constant here is slightly subtle.3208        // There are two independent reasons:3209        // - We assume that things which are constant (from LLVM's definition)3210        // do not move at runtime.  For example, the address of a global3211        // variable is fixed, even though it's contents may not be.3212        // - Second, we can't disallow arbitrary inttoptr constants even3213        // if the language frontend does.  Optimization passes are free to3214        // locally exploit facts without respect to global reachability.  This3215        // can create sections of code which are dynamically unreachable and3216        // contain just about anything.  (see constants.ll in tests)3217        LiveTmp.insert(V);3218      }3219    }3220  }3221}3222 3223static void computeLiveOutSeed(BasicBlock *BB, SetVector<Value *> &LiveTmp,3224                               GCStrategy *GC) {3225  for (BasicBlock *Succ : successors(BB)) {3226    for (auto &I : *Succ) {3227      PHINode *PN = dyn_cast<PHINode>(&I);3228      if (!PN)3229        break;3230 3231      Value *V = PN->getIncomingValueForBlock(BB);3232      assert(!isUnhandledGCPointerType(V->getType(), GC) &&3233             "support for FCA unimplemented");3234      if (isHandledGCPointerType(V->getType(), GC) && !isa<Constant>(V))3235        LiveTmp.insert(V);3236    }3237  }3238}3239 3240static SetVector<Value *> computeKillSet(BasicBlock *BB, GCStrategy *GC) {3241  SetVector<Value *> KillSet;3242  for (Instruction &I : *BB)3243    if (isHandledGCPointerType(I.getType(), GC))3244      KillSet.insert(&I);3245  return KillSet;3246}3247 3248#ifndef NDEBUG3249/// Check that the items in 'Live' dominate 'TI'.  This is used as a basic3250/// validation check for the liveness computation.3251static void checkBasicSSA(DominatorTree &DT, SetVector<Value *> &Live,3252                          Instruction *TI, bool TermOkay = false) {3253  for (Value *V : Live) {3254    if (auto *I = dyn_cast<Instruction>(V)) {3255      // The terminator can be a member of the LiveOut set.  LLVM's definition3256      // of instruction dominance states that V does not dominate itself.  As3257      // such, we need to special case this to allow it.3258      if (TermOkay && TI == I)3259        continue;3260      assert(DT.dominates(I, TI) &&3261             "basic SSA liveness expectation violated by liveness analysis");3262    }3263  }3264}3265 3266/// Check that all the liveness sets used during the computation of liveness3267/// obey basic SSA properties.  This is useful for finding cases where we miss3268/// a def.3269static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,3270                          BasicBlock &BB) {3271  checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator());3272  checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);3273  checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());3274}3275#endif3276 3277static void computeLiveInValues(DominatorTree &DT, Function &F,3278                                GCPtrLivenessData &Data, GCStrategy *GC) {3279  SmallSetVector<BasicBlock *, 32> Worklist;3280 3281  // Seed the liveness for each individual block3282  for (BasicBlock &BB : F) {3283    Data.KillSet[&BB] = computeKillSet(&BB, GC);3284    auto &LiveSet = Data.LiveSet[&BB];3285    LiveSet.clear();3286    computeLiveInValues(BB.rbegin(), BB.rend(), LiveSet, GC);3287 3288#ifndef NDEBUG3289    for (Value *Kill : Data.KillSet[&BB])3290      assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");3291#endif3292 3293    auto &Out = Data.LiveOut[&BB] = SetVector<Value *>();3294    computeLiveOutSeed(&BB, Out, GC);3295    auto &In = Data.LiveIn[&BB] = Data.LiveSet[&BB];3296    In.set_union(Out);3297    In.set_subtract(Data.KillSet[&BB]);3298    if (!In.empty())3299      Worklist.insert_range(predecessors(&BB));3300  }3301 3302  // Propagate that liveness until stable3303  while (!Worklist.empty()) {3304    BasicBlock *BB = Worklist.pop_back_val();3305 3306    // Compute our new liveout set, then exit early if it hasn't changed despite3307    // the contribution of our successor.3308    SetVector<Value *> &LiveOut = Data.LiveOut[BB];3309    const auto OldLiveOutSize = LiveOut.size();3310    for (BasicBlock *Succ : successors(BB)) {3311      assert(Data.LiveIn.count(Succ));3312      LiveOut.set_union(Data.LiveIn[Succ]);3313    }3314    // assert OutLiveOut is a subset of LiveOut3315    if (OldLiveOutSize == LiveOut.size()) {3316      // If the sets are the same size, then we didn't actually add anything3317      // when unioning our successors LiveIn.  Thus, the LiveIn of this block3318      // hasn't changed.3319      continue;3320    }3321 3322    // Apply the effects of this basic block3323    SetVector<Value *> LiveTmp = LiveOut;3324    LiveTmp.set_union(Data.LiveSet[BB]);3325    LiveTmp.set_subtract(Data.KillSet[BB]);3326 3327    assert(Data.LiveIn.count(BB));3328    SetVector<Value *> &LiveIn = Data.LiveIn[BB];3329    // assert: LiveIn is a subset of LiveTmp3330    if (LiveIn.size() != LiveTmp.size()) {3331      LiveIn = std::move(LiveTmp);3332      Worklist.insert_range(predecessors(BB));3333    }3334  } // while (!Worklist.empty())3335 3336#ifndef NDEBUG3337  // Verify our output against SSA properties.  This helps catch any3338  // missing kills during the above iteration.3339  for (BasicBlock &BB : F)3340    checkBasicSSA(DT, Data, BB);3341#endif3342}3343 3344static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,3345                              StatepointLiveSetTy &Out, GCStrategy *GC) {3346  BasicBlock *BB = Inst->getParent();3347 3348  // Note: The copy is intentional and required3349  assert(Data.LiveOut.count(BB));3350  SetVector<Value *> LiveOut = Data.LiveOut[BB];3351 3352  // We want to handle the statepoint itself oddly.  It's3353  // call result is not live (normal), nor are it's arguments3354  // (unless they're used again later).  This adjustment is3355  // specifically what we need to relocate3356  computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(), LiveOut,3357                      GC);3358  LiveOut.remove(Inst);3359  Out.insert_range(LiveOut);3360}3361 3362static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,3363                                  CallBase *Call,3364                                  PartiallyConstructedSafepointRecord &Info,3365                                  PointerToBaseTy &PointerToBase,3366                                  GCStrategy *GC) {3367  StatepointLiveSetTy Updated;3368  findLiveSetAtInst(Call, RevisedLivenessData, Updated, GC);3369 3370  // We may have base pointers which are now live that weren't before.  We need3371  // to update the PointerToBase structure to reflect this.3372  for (auto *V : Updated)3373    PointerToBase.insert({ V, V });3374 3375  Info.LiveSet = Updated;3376}3377