diff options
Diffstat (limited to 'lib/Transforms/Scalar/RewriteStatepointsForGC.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/RewriteStatepointsForGC.cpp | 1035 |
1 files changed, 359 insertions, 676 deletions
diff --git a/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp b/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp index d77d5745e60c..bab39a32677f 100644 --- a/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ b/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -14,7 +14,6 @@ #include "llvm/Pass.h" #include "llvm/Analysis/CFG.h" -#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/ADT/SetOperations.h" #include "llvm/ADT/Statistic.h" @@ -63,7 +62,7 @@ static cl::opt<unsigned> RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden, cl::init(6)); -#ifdef XDEBUG +#ifdef EXPENSIVE_CHECKS static bool ClobberNonLive = true; #else static bool ClobberNonLive = false; @@ -72,19 +71,10 @@ static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live", cl::location(ClobberNonLive), cl::Hidden); -static cl::opt<bool> UseDeoptBundles("rs4gc-use-deopt-bundles", cl::Hidden, - cl::init(false)); static cl::opt<bool> AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", cl::Hidden, cl::init(true)); -/// Should we split vectors of pointers into their individual elements? This -/// is known to be buggy, but the alternate implementation isn't yet ready. -/// This is purely to provide a debugging and dianostic hook until the vector -/// split is replaced with vector relocations. -static cl::opt<bool> UseVectorSplit("rs4gc-split-vector-values", cl::Hidden, - cl::init(true)); - namespace { struct RewriteStatepointsForGC : public ModulePass { static char ID; // Pass identification, replacement for typeid @@ -141,24 +131,25 @@ ModulePass *llvm::createRewriteStatepointsForGCPass() { INITIALIZE_PASS_BEGIN(RewriteStatepointsForGC, "rewrite-statepoints-for-gc", "Make relocations explicit at statepoints", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_END(RewriteStatepointsForGC, "rewrite-statepoints-for-gc", "Make relocations explicit at statepoints", false, false) namespace { struct GCPtrLivenessData { /// Values defined in this block. - DenseMap<BasicBlock *, DenseSet<Value *>> KillSet; + MapVector<BasicBlock *, SetVector<Value *>> KillSet; /// Values used in this block (and thus live); does not included values /// killed within this block. - DenseMap<BasicBlock *, DenseSet<Value *>> LiveSet; + MapVector<BasicBlock *, SetVector<Value *>> LiveSet; /// Values live into this basic block (i.e. used by any /// instruction in this basic block or ones reachable from here) - DenseMap<BasicBlock *, DenseSet<Value *>> LiveIn; + MapVector<BasicBlock *, SetVector<Value *>> LiveIn; /// Values live out of this basic block (i.e. live into /// any successor block) - DenseMap<BasicBlock *, DenseSet<Value *>> LiveOut; + MapVector<BasicBlock *, SetVector<Value *>> LiveOut; }; // The type of the internal cache used inside the findBasePointers family @@ -171,9 +162,9 @@ struct GCPtrLivenessData { // Generally, after the execution of a full findBasePointer call, only the // base relation will remain. Internally, we add a mixture of the two // types, then update all the second type to the first type -typedef DenseMap<Value *, Value *> DefiningValueMapTy; -typedef DenseSet<Value *> StatepointLiveSetTy; -typedef DenseMap<AssertingVH<Instruction>, AssertingVH<Value>> +typedef MapVector<Value *, Value *> DefiningValueMapTy; +typedef SetVector<Value *> StatepointLiveSetTy; +typedef MapVector<AssertingVH<Instruction>, AssertingVH<Value>> RematerializedValueMapTy; struct PartiallyConstructedSafepointRecord { @@ -181,7 +172,7 @@ struct PartiallyConstructedSafepointRecord { StatepointLiveSetTy LiveSet; /// Mapping from live pointers to a base-defining-value - DenseMap<Value *, Value *> PointerToBase; + MapVector<Value *, Value *> PointerToBase; /// The *new* gc.statepoint instruction itself. This produces the token /// that normal path gc.relocates and the gc.result are tied to. @@ -199,9 +190,8 @@ struct PartiallyConstructedSafepointRecord { } static ArrayRef<Use> GetDeoptBundleOperands(ImmutableCallSite CS) { - assert(UseDeoptBundles && "Should not be called otherwise!"); - - Optional<OperandBundleUse> DeoptBundle = CS.getOperandBundle("deopt"); + Optional<OperandBundleUse> DeoptBundle = + CS.getOperandBundle(LLVMContext::OB_deopt); if (!DeoptBundle.hasValue()) { assert(AllowStatepointWithNoDeoptInfo && @@ -229,7 +219,7 @@ static bool isGCPointerType(Type *T) { // For the sake of this example GC, we arbitrarily pick addrspace(1) as our // GC managed heap. We know that a pointer into this heap needs to be // updated and that no other pointer does. - return (1 == PT->getAddressSpace()); + return PT->getAddressSpace() == 1; return false; } @@ -260,8 +250,7 @@ static bool containsGCPtrType(Type *Ty) { if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) return containsGCPtrType(AT->getElementType()); if (StructType *ST = dyn_cast<StructType>(Ty)) - return std::any_of(ST->subtypes().begin(), ST->subtypes().end(), - containsGCPtrType); + return any_of(ST->subtypes(), containsGCPtrType); return false; } @@ -273,19 +262,6 @@ static bool isUnhandledGCPointerType(Type *Ty) { } #endif -static bool order_by_name(Value *a, Value *b) { - if (a->hasName() && b->hasName()) { - return -1 == a->getName().compare(b->getName()); - } else if (a->hasName() && !b->hasName()) { - return true; - } else if (!a->hasName() && b->hasName()) { - return false; - } else { - // Better than nothing, but not stable - return a < b; - } -} - // Return the name of the value suffixed with the provided value, or if the // value didn't have a name, the default value specified. static std::string suffixed_name_or(Value *V, StringRef Suffix, @@ -297,30 +273,25 @@ static std::string suffixed_name_or(Value *V, StringRef Suffix, // given instruction. The analysis is performed immediately before the // given instruction. Values defined by that instruction are not considered // live. Values used by that instruction are considered live. -static void analyzeParsePointLiveness( - DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, - const CallSite &CS, PartiallyConstructedSafepointRecord &result) { - Instruction *inst = CS.getInstruction(); +static void +analyzeParsePointLiveness(DominatorTree &DT, + GCPtrLivenessData &OriginalLivenessData, CallSite CS, + PartiallyConstructedSafepointRecord &Result) { + Instruction *Inst = CS.getInstruction(); StatepointLiveSetTy LiveSet; - findLiveSetAtInst(inst, OriginalLivenessData, LiveSet); + findLiveSetAtInst(Inst, OriginalLivenessData, LiveSet); if (PrintLiveSet) { - // Note: This output is used by several of the test cases - // The order of elements in a set is not stable, put them in a vec and sort - // by name - SmallVector<Value *, 64> Temp; - Temp.insert(Temp.end(), LiveSet.begin(), LiveSet.end()); - std::sort(Temp.begin(), Temp.end(), order_by_name); - errs() << "Live Variables:\n"; - for (Value *V : Temp) + dbgs() << "Live Variables:\n"; + for (Value *V : LiveSet) dbgs() << " " << V->getName() << " " << *V << "\n"; } if (PrintLiveSetSize) { - errs() << "Safepoint For: " << CS.getCalledValue()->getName() << "\n"; - errs() << "Number live values: " << LiveSet.size() << "\n"; + dbgs() << "Safepoint For: " << CS.getCalledValue()->getName() << "\n"; + dbgs() << "Number live values: " << LiveSet.size() << "\n"; } - result.LiveSet = LiveSet; + Result.LiveSet = LiveSet; } static bool isKnownBaseResult(Value *V); @@ -372,8 +343,10 @@ findBaseDefiningValueOfVector(Value *I) { return BaseDefiningValueResult(I, true); if (isa<Constant>(I)) - // Constant vectors consist only of constant pointers. - return BaseDefiningValueResult(I, true); + // Base of constant vector consists only of constant null pointers. + // For reasoning see similar case inside 'findBaseDefiningValue' function. + return BaseDefiningValueResult(ConstantAggregateZero::get(I->getType()), + true); if (isa<LoadInst>(I)) return BaseDefiningValueResult(I, true); @@ -415,14 +388,20 @@ static BaseDefiningValueResult findBaseDefiningValue(Value *I) { // We should have never reached here if this argument isn't an gc value return BaseDefiningValueResult(I, true); - if (isa<Constant>(I)) + if (isa<Constant>(I)) { // We assume that objects with a constant base (e.g. a global) can't move // and don't need to be reported to the collector because they are always - // live. All constants have constant bases. Besides global references, all - // kinds of constants (e.g. undef, constant expressions, null pointers) can - // be introduced by the inliner or the optimizer, especially on dynamically - // dead paths. See e.g. test4 in constants.ll. - return BaseDefiningValueResult(I, true); + // live. Besides global references, all kinds of constants (e.g. undef, + // constant expressions, null pointers) can be introduced by the inliner or + // the optimizer, especially on dynamically dead paths. + // Here we treat all of them as having single null base. By doing this we + // trying to avoid problems reporting various conflicts in a form of + // "phi (const1, const2)" or "phi (const, regular gc ptr)". + // See constant.ll file for relevant test cases. + + return BaseDefiningValueResult( + ConstantPointerNull::get(cast<PointerType>(I->getType())), true); + } if (CastInst *CI = dyn_cast<CastInst>(I)) { Value *Def = CI->stripPointerCasts(); @@ -570,30 +549,36 @@ class BDVState { public: enum Status { Unknown, Base, Conflict }; - BDVState(Status s, Value *b = nullptr) : status(s), base(b) { - assert(status != Base || b); + BDVState() : Status(Unknown), BaseValue(nullptr) {} + + explicit BDVState(Status Status, Value *BaseValue = nullptr) + : Status(Status), BaseValue(BaseValue) { + assert(Status != Base || BaseValue); } - explicit BDVState(Value *b) : status(Base), base(b) {} - BDVState() : status(Unknown), base(nullptr) {} - Status getStatus() const { return status; } - Value *getBase() const { return base; } + explicit BDVState(Value *BaseValue) : Status(Base), BaseValue(BaseValue) {} + + Status getStatus() const { return Status; } + Value *getBaseValue() const { return BaseValue; } bool isBase() const { return getStatus() == Base; } bool isUnknown() const { return getStatus() == Unknown; } bool isConflict() const { return getStatus() == Conflict; } - bool operator==(const BDVState &other) const { - return base == other.base && status == other.status; + bool operator==(const BDVState &Other) const { + return BaseValue == Other.BaseValue && Status == Other.Status; } bool operator!=(const BDVState &other) const { return !(*this == other); } LLVM_DUMP_METHOD - void dump() const { print(dbgs()); dbgs() << '\n'; } - + void dump() const { + print(dbgs()); + dbgs() << '\n'; + } + void print(raw_ostream &OS) const { - switch (status) { + switch (getStatus()) { case Unknown: OS << "U"; break; @@ -604,13 +589,13 @@ public: OS << "C"; break; }; - OS << " (" << base << " - " - << (base ? base->getName() : "nullptr") << "): "; + OS << " (" << getBaseValue() << " - " + << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << "): "; } private: - Status status; - AssertingVH<Value> base; // non null only if status == base + Status Status; + AssertingVH<Value> BaseValue; // Non-null only if Status == Base. }; } @@ -621,75 +606,50 @@ static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) { } #endif -namespace { -// Values of type BDVState form a lattice, and this is a helper -// class that implementes the meet operation. The meat of the meet -// operation is implemented in MeetBDVStates::pureMeet -class MeetBDVStates { -public: - /// Initializes the currentResult to the TOP state so that if can be met with - /// any other state to produce that state. - MeetBDVStates() {} - - // Destructively meet the current result with the given BDVState - void meetWith(BDVState otherState) { - currentResult = meet(otherState, currentResult); - } +static BDVState meetBDVStateImpl(const BDVState &LHS, const BDVState &RHS) { + switch (LHS.getStatus()) { + case BDVState::Unknown: + return RHS; - BDVState getResult() const { return currentResult; } + case BDVState::Base: + assert(LHS.getBaseValue() && "can't be null"); + if (RHS.isUnknown()) + return LHS; -private: - BDVState currentResult; - - /// Perform a meet operation on two elements of the BDVState lattice. - static BDVState meet(BDVState LHS, BDVState RHS) { - assert((pureMeet(LHS, RHS) == pureMeet(RHS, LHS)) && - "math is wrong: meet does not commute!"); - BDVState Result = pureMeet(LHS, RHS); - DEBUG(dbgs() << "meet of " << LHS << " with " << RHS - << " produced " << Result << "\n"); - return Result; - } - - static BDVState pureMeet(const BDVState &stateA, const BDVState &stateB) { - switch (stateA.getStatus()) { - case BDVState::Unknown: - return stateB; - - case BDVState::Base: - assert(stateA.getBase() && "can't be null"); - if (stateB.isUnknown()) - return stateA; - - if (stateB.isBase()) { - if (stateA.getBase() == stateB.getBase()) { - assert(stateA == stateB && "equality broken!"); - return stateA; - } - return BDVState(BDVState::Conflict); + if (RHS.isBase()) { + if (LHS.getBaseValue() == RHS.getBaseValue()) { + assert(LHS == RHS && "equality broken!"); + return LHS; } - assert(stateB.isConflict() && "only three states!"); return BDVState(BDVState::Conflict); - - case BDVState::Conflict: - return stateA; } - llvm_unreachable("only three states!"); + assert(RHS.isConflict() && "only three states!"); + return BDVState(BDVState::Conflict); + + case BDVState::Conflict: + return LHS; } -}; + llvm_unreachable("only three states!"); } +// Values of type BDVState form a lattice, and this function implements the meet +// operation. +static BDVState meetBDVState(BDVState LHS, BDVState RHS) { + BDVState Result = meetBDVStateImpl(LHS, RHS); + assert(Result == meetBDVStateImpl(RHS, LHS) && + "Math is wrong: meet does not commute!"); + return Result; +} -/// For a given value or instruction, figure out what base ptr it's derived -/// from. For gc objects, this is simply itself. On success, returns a value -/// which is the base pointer. (This is reliable and can be used for -/// relocation.) On failure, returns nullptr. -static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { - Value *def = findBaseOrBDV(I, cache); +/// For a given value or instruction, figure out what base ptr its derived from. +/// For gc objects, this is simply itself. On success, returns a value which is +/// the base pointer. (This is reliable and can be used for relocation.) On +/// failure, returns nullptr. +static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache) { + Value *Def = findBaseOrBDV(I, Cache); - if (isKnownBaseResult(def)) { - return def; - } + if (isKnownBaseResult(Def)) + return Def; // Here's the rough algorithm: // - For every SSA value, construct a mapping to either an actual base @@ -731,14 +691,14 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // one for which we don't already know a definite base value for /* scope */ { SmallVector<Value*, 16> Worklist; - Worklist.push_back(def); - States.insert(std::make_pair(def, BDVState())); + Worklist.push_back(Def); + States.insert({Def, BDVState()}); while (!Worklist.empty()) { Value *Current = Worklist.pop_back_val(); assert(!isKnownBaseResult(Current) && "why did it get added?"); auto visitIncomingValue = [&](Value *InVal) { - Value *Base = findBaseOrBDV(InVal, cache); + Value *Base = findBaseOrBDV(InVal, Cache); if (isKnownBaseResult(Base)) // Known bases won't need new instructions introduced and can be // ignored safely @@ -748,12 +708,12 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { if (States.insert(std::make_pair(Base, BDVState())).second) Worklist.push_back(Base); }; - if (PHINode *Phi = dyn_cast<PHINode>(Current)) { - for (Value *InVal : Phi->incoming_values()) + if (PHINode *PN = dyn_cast<PHINode>(Current)) { + for (Value *InVal : PN->incoming_values()) visitIncomingValue(InVal); - } else if (SelectInst *Sel = dyn_cast<SelectInst>(Current)) { - visitIncomingValue(Sel->getTrueValue()); - visitIncomingValue(Sel->getFalseValue()); + } else if (SelectInst *SI = dyn_cast<SelectInst>(Current)) { + visitIncomingValue(SI->getTrueValue()); + visitIncomingValue(SI->getFalseValue()); } else if (auto *EE = dyn_cast<ExtractElementInst>(Current)) { visitIncomingValue(EE->getVectorOperand()); } else if (auto *IE = dyn_cast<InsertElementInst>(Current)) { @@ -762,7 +722,7 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { } else { // There is one known class of instructions we know we don't handle. assert(isa<ShuffleVectorInst>(Current)); - llvm_unreachable("unimplemented instruction case"); + llvm_unreachable("Unimplemented instruction case"); } } } @@ -784,12 +744,12 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { return I->second; }; - bool progress = true; - while (progress) { + bool Progress = true; + while (Progress) { #ifndef NDEBUG - const size_t oldSize = States.size(); + const size_t OldSize = States.size(); #endif - progress = false; + Progress = false; // We're only changing values in this loop, thus safe to keep iterators. // Since this is computing a fixed point, the order of visit does not // effect the result. TODO: We could use a worklist here and make this run @@ -801,38 +761,39 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // Given an input value for the current instruction, return a BDVState // instance which represents the BDV of that value. auto getStateForInput = [&](Value *V) mutable { - Value *BDV = findBaseOrBDV(V, cache); + Value *BDV = findBaseOrBDV(V, Cache); return getStateForBDV(BDV); }; - MeetBDVStates calculateMeet; - if (SelectInst *select = dyn_cast<SelectInst>(BDV)) { - calculateMeet.meetWith(getStateForInput(select->getTrueValue())); - calculateMeet.meetWith(getStateForInput(select->getFalseValue())); - } else if (PHINode *Phi = dyn_cast<PHINode>(BDV)) { - for (Value *Val : Phi->incoming_values()) - calculateMeet.meetWith(getStateForInput(Val)); + BDVState NewState; + if (SelectInst *SI = dyn_cast<SelectInst>(BDV)) { + NewState = meetBDVState(NewState, getStateForInput(SI->getTrueValue())); + NewState = + meetBDVState(NewState, getStateForInput(SI->getFalseValue())); + } else if (PHINode *PN = dyn_cast<PHINode>(BDV)) { + for (Value *Val : PN->incoming_values()) + NewState = meetBDVState(NewState, getStateForInput(Val)); } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) { // The 'meet' for an extractelement is slightly trivial, but it's still // useful in that it drives us to conflict if our input is. - calculateMeet.meetWith(getStateForInput(EE->getVectorOperand())); + NewState = + meetBDVState(NewState, getStateForInput(EE->getVectorOperand())); } else { // Given there's a inherent type mismatch between the operands, will // *always* produce Conflict. auto *IE = cast<InsertElementInst>(BDV); - calculateMeet.meetWith(getStateForInput(IE->getOperand(0))); - calculateMeet.meetWith(getStateForInput(IE->getOperand(1))); + NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(0))); + NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(1))); } - BDVState oldState = States[BDV]; - BDVState newState = calculateMeet.getResult(); - if (oldState != newState) { - progress = true; - States[BDV] = newState; + BDVState OldState = States[BDV]; + if (OldState != NewState) { + Progress = true; + States[BDV] = NewState; } } - assert(oldSize == States.size() && + assert(OldSize == States.size() && "fixed point shouldn't be adding any new nodes to state"); } @@ -842,7 +803,7 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n"); } #endif - + // Insert Phis for all conflicts // TODO: adjust naming patterns to avoid this order of iteration dependency for (auto Pair : States) { @@ -856,14 +817,13 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // The problem is that we need to convert from a vector base to a scalar // base for the particular indice we're interested in. if (State.isBase() && isa<ExtractElementInst>(I) && - isa<VectorType>(State.getBase()->getType())) { + isa<VectorType>(State.getBaseValue()->getType())) { auto *EE = cast<ExtractElementInst>(I); // TODO: In many cases, the new instruction is just EE itself. We should // exploit this, but can't do it here since it would break the invariant // about the BDV not being known to be a base. - auto *BaseInst = ExtractElementInst::Create(State.getBase(), - EE->getIndexOperand(), - "base_ee", EE); + auto *BaseInst = ExtractElementInst::Create( + State.getBaseValue(), EE->getIndexOperand(), "base_ee", EE); BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {})); States[I] = BDVState(BDVState::Base, BaseInst); } @@ -871,10 +831,8 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // Since we're joining a vector and scalar base, they can never be the // same. As a result, we should always see insert element having reached // the conflict state. - if (isa<InsertElementInst>(I)) { - assert(State.isConflict()); - } - + assert(!isa<InsertElementInst>(I) || State.isConflict()); + if (!State.isConflict()) continue; @@ -887,12 +845,11 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { assert(NumPreds > 0 && "how did we reach here"); std::string Name = suffixed_name_or(I, ".base", "base_phi"); return PHINode::Create(I->getType(), NumPreds, Name, I); - } else if (SelectInst *Sel = dyn_cast<SelectInst>(I)) { + } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) { // The undef will be replaced later - UndefValue *Undef = UndefValue::get(Sel->getType()); + UndefValue *Undef = UndefValue::get(SI->getType()); std::string Name = suffixed_name_or(I, ".base", "base_select"); - return SelectInst::Create(Sel->getCondition(), Undef, - Undef, Name, Sel); + return SelectInst::Create(SI->getCondition(), Undef, Undef, Name, SI); } else if (auto *EE = dyn_cast<ExtractElementInst>(I)) { UndefValue *Undef = UndefValue::get(EE->getVectorOperand()->getType()); std::string Name = suffixed_name_or(I, ".base", "base_ee"); @@ -906,7 +863,6 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { return InsertElementInst::Create(VecUndef, ScalarUndef, IE->getOperand(2), Name, IE); } - }; Instruction *BaseInst = MakeBaseInstPlaceholder(I); // Add metadata marking this as a base value @@ -921,24 +877,21 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // instruction to propagate the base of it's BDV and have entered that newly // introduced instruction into the state table. In either case, we are // assured to be able to determine an instruction which produces it's base - // pointer. + // pointer. auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) { - Value *BDV = findBaseOrBDV(Input, cache); + Value *BDV = findBaseOrBDV(Input, Cache); Value *Base = nullptr; if (isKnownBaseResult(BDV)) { Base = BDV; } else { // Either conflict or base. assert(States.count(BDV)); - Base = States[BDV].getBase(); + Base = States[BDV].getBaseValue(); } - assert(Base && "can't be null"); + assert(Base && "Can't be null"); // The cast is needed since base traversal may strip away bitcasts - if (Base->getType() != Input->getType() && - InsertPt) { - Base = new BitCastInst(Base, Input->getType(), "cast", - InsertPt); - } + if (Base->getType() != Input->getType() && InsertPt) + Base = new BitCastInst(Base, Input->getType(), "cast", InsertPt); return Base; }; @@ -954,12 +907,12 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { if (!State.isConflict()) continue; - if (PHINode *basephi = dyn_cast<PHINode>(State.getBase())) { - PHINode *phi = cast<PHINode>(BDV); - unsigned NumPHIValues = phi->getNumIncomingValues(); + if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) { + PHINode *PN = cast<PHINode>(BDV); + unsigned NumPHIValues = PN->getNumIncomingValues(); for (unsigned i = 0; i < NumPHIValues; i++) { - Value *InVal = phi->getIncomingValue(i); - BasicBlock *InBB = phi->getIncomingBlock(i); + Value *InVal = PN->getIncomingValue(i); + BasicBlock *InBB = PN->getIncomingBlock(i); // If we've already seen InBB, add the same incoming value // we added for it earlier. The IR verifier requires phi @@ -970,22 +923,21 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // bitcasts (and hence two distinct values) as incoming // values for the same basic block. - int blockIndex = basephi->getBasicBlockIndex(InBB); - if (blockIndex != -1) { - Value *oldBase = basephi->getIncomingValue(blockIndex); - basephi->addIncoming(oldBase, InBB); - + int BlockIndex = BasePHI->getBasicBlockIndex(InBB); + if (BlockIndex != -1) { + Value *OldBase = BasePHI->getIncomingValue(BlockIndex); + BasePHI->addIncoming(OldBase, InBB); + #ifndef NDEBUG Value *Base = getBaseForInput(InVal, nullptr); - // In essence this assert states: the only way two - // values incoming from the same basic block may be - // different is by being different bitcasts of the same - // value. A cleanup that remains TODO is changing - // findBaseOrBDV to return an llvm::Value of the correct - // type (and still remain pure). This will remove the - // need to add bitcasts. - assert(Base->stripPointerCasts() == oldBase->stripPointerCasts() && - "sanity -- findBaseOrBDV should be pure!"); + // In essence this assert states: the only way two values + // incoming from the same basic block may be different is by + // being different bitcasts of the same value. A cleanup + // that remains TODO is changing findBaseOrBDV to return an + // llvm::Value of the correct type (and still remain pure). + // This will remove the need to add bitcasts. + assert(Base->stripPointerCasts() == OldBase->stripPointerCasts() && + "Sanity -- findBaseOrBDV should be pure!"); #endif continue; } @@ -994,28 +946,25 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // need to insert a bitcast in the incoming block. // TODO: Need to split critical edges if insertion is needed Value *Base = getBaseForInput(InVal, InBB->getTerminator()); - basephi->addIncoming(Base, InBB); + BasePHI->addIncoming(Base, InBB); } - assert(basephi->getNumIncomingValues() == NumPHIValues); - } else if (SelectInst *BaseSel = dyn_cast<SelectInst>(State.getBase())) { - SelectInst *Sel = cast<SelectInst>(BDV); - // Operand 1 & 2 are true, false path respectively. TODO: refactor to - // something more safe and less hacky. - for (int i = 1; i <= 2; i++) { - Value *InVal = Sel->getOperand(i); - // Find the instruction which produces the base for each input. We may - // need to insert a bitcast. - Value *Base = getBaseForInput(InVal, BaseSel); - BaseSel->setOperand(i, Base); - } - } else if (auto *BaseEE = dyn_cast<ExtractElementInst>(State.getBase())) { + assert(BasePHI->getNumIncomingValues() == NumPHIValues); + } else if (SelectInst *BaseSI = + dyn_cast<SelectInst>(State.getBaseValue())) { + SelectInst *SI = cast<SelectInst>(BDV); + + // Find the instruction which produces the base for each input. + // We may need to insert a bitcast. + BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI)); + BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI)); + } else if (auto *BaseEE = + dyn_cast<ExtractElementInst>(State.getBaseValue())) { Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand(); // Find the instruction which produces the base for each input. We may // need to insert a bitcast. - Value *Base = getBaseForInput(InVal, BaseEE); - BaseEE->setOperand(0, Base); + BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE)); } else { - auto *BaseIE = cast<InsertElementInst>(State.getBase()); + auto *BaseIE = cast<InsertElementInst>(State.getBaseValue()); auto *BdvIE = cast<InsertElementInst>(BDV); auto UpdateOperand = [&](int OperandIdx) { Value *InVal = BdvIE->getOperand(OperandIdx); @@ -1025,69 +974,6 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { UpdateOperand(0); // vector operand UpdateOperand(1); // scalar operand } - - } - - // Now that we're done with the algorithm, see if we can optimize the - // results slightly by reducing the number of new instructions needed. - // Arguably, this should be integrated into the algorithm above, but - // doing as a post process step is easier to reason about for the moment. - DenseMap<Value *, Value *> ReverseMap; - SmallPtrSet<Instruction *, 16> NewInsts; - SmallSetVector<AssertingVH<Instruction>, 16> Worklist; - // Note: We need to visit the states in a deterministic order. We uses the - // Keys we sorted above for this purpose. Note that we are papering over a - // bigger problem with the algorithm above - it's visit order is not - // deterministic. A larger change is needed to fix this. - for (auto Pair : States) { - auto *BDV = Pair.first; - auto State = Pair.second; - Value *Base = State.getBase(); - assert(BDV && Base); - assert(!isKnownBaseResult(BDV) && "why did it get added?"); - assert(isKnownBaseResult(Base) && - "must be something we 'know' is a base pointer"); - if (!State.isConflict()) - continue; - - ReverseMap[Base] = BDV; - if (auto *BaseI = dyn_cast<Instruction>(Base)) { - NewInsts.insert(BaseI); - Worklist.insert(BaseI); - } - } - auto ReplaceBaseInstWith = [&](Value *BDV, Instruction *BaseI, - Value *Replacement) { - // Add users which are new instructions (excluding self references) - for (User *U : BaseI->users()) - if (auto *UI = dyn_cast<Instruction>(U)) - if (NewInsts.count(UI) && UI != BaseI) - Worklist.insert(UI); - // Then do the actual replacement - NewInsts.erase(BaseI); - ReverseMap.erase(BaseI); - BaseI->replaceAllUsesWith(Replacement); - assert(States.count(BDV)); - assert(States[BDV].isConflict() && States[BDV].getBase() == BaseI); - States[BDV] = BDVState(BDVState::Conflict, Replacement); - BaseI->eraseFromParent(); - }; - const DataLayout &DL = cast<Instruction>(def)->getModule()->getDataLayout(); - while (!Worklist.empty()) { - Instruction *BaseI = Worklist.pop_back_val(); - assert(NewInsts.count(BaseI)); - Value *Bdv = ReverseMap[BaseI]; - if (auto *BdvI = dyn_cast<Instruction>(Bdv)) - if (BaseI->isIdenticalTo(BdvI)) { - DEBUG(dbgs() << "Identical Base: " << *BaseI << "\n"); - ReplaceBaseInstWith(Bdv, BaseI, Bdv); - continue; - } - if (Value *V = SimplifyInstruction(BaseI, DL)) { - DEBUG(dbgs() << "Base " << *BaseI << " simplified to " << *V << "\n"); - ReplaceBaseInstWith(Bdv, BaseI, V); - continue; - } } // Cache all of our results so we can cheaply reuse them @@ -1095,25 +981,27 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // relation and one of the base pointer relation! FIXME for (auto Pair : States) { auto *BDV = Pair.first; - Value *base = Pair.second.getBase(); - assert(BDV && base); + Value *Base = Pair.second.getBaseValue(); + assert(BDV && Base); + assert(!isKnownBaseResult(BDV) && "why did it get added?"); - std::string fromstr = cache.count(BDV) ? cache[BDV]->getName() : "none"; DEBUG(dbgs() << "Updating base value cache" - << " for: " << BDV->getName() - << " from: " << fromstr - << " to: " << base->getName() << "\n"); - - if (cache.count(BDV)) { - // Once we transition from the BDV relation being store in the cache to + << " for: " << BDV->getName() << " from: " + << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none") + << " to: " << Base->getName() << "\n"); + + if (Cache.count(BDV)) { + assert(isKnownBaseResult(Base) && + "must be something we 'know' is a base pointer"); + // Once we transition from the BDV relation being store in the Cache to // the base relation being stored, it must be stable - assert((!isKnownBaseResult(cache[BDV]) || cache[BDV] == base) && + assert((!isKnownBaseResult(Cache[BDV]) || Cache[BDV] == Base) && "base relation should be stable"); } - cache[BDV] = base; + Cache[BDV] = Base; } - assert(cache.count(def)); - return cache[def]; + assert(Cache.count(Def)); + return Cache[Def]; } // For a set of live pointers (base and/or derived), identify the base @@ -1133,15 +1021,9 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) { // pointer was a base pointer. static void findBasePointers(const StatepointLiveSetTy &live, - DenseMap<Value *, Value *> &PointerToBase, + MapVector<Value *, Value *> &PointerToBase, DominatorTree *DT, DefiningValueMapTy &DVCache) { - // For the naming of values inserted to be deterministic - which makes for - // much cleaner and more stable tests - we need to assign an order to the - // live values. DenseSets do not provide a deterministic order across runs. - SmallVector<Value *, 64> Temp; - Temp.insert(Temp.end(), live.begin(), live.end()); - std::sort(Temp.begin(), Temp.end(), order_by_name); - for (Value *ptr : Temp) { + for (Value *ptr : live) { Value *base = findBasePointer(ptr, DVCache); assert(base && "failed to find base pointer"); PointerToBase[ptr] = base; @@ -1149,41 +1031,24 @@ findBasePointers(const StatepointLiveSetTy &live, DT->dominates(cast<Instruction>(base)->getParent(), cast<Instruction>(ptr)->getParent())) && "The base we found better dominate the derived pointer"); - - // If you see this trip and like to live really dangerously, the code should - // be correct, just with idioms the verifier can't handle. You can try - // disabling the verifier at your own substantial risk. - assert(!isa<ConstantPointerNull>(base) && - "the relocation code needs adjustment to handle the relocation of " - "a null pointer constant without causing false positives in the " - "safepoint ir verifier."); } } /// Find the required based pointers (and adjust the live set) for the given /// parse point. static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache, - const CallSite &CS, + CallSite CS, PartiallyConstructedSafepointRecord &result) { - DenseMap<Value *, Value *> PointerToBase; + MapVector<Value *, Value *> PointerToBase; findBasePointers(result.LiveSet, PointerToBase, &DT, DVCache); if (PrintBasePointers) { - // Note: Need to print these in a stable order since this is checked in - // some tests. errs() << "Base Pairs (w/o Relocation):\n"; - SmallVector<Value *, 64> Temp; - Temp.reserve(PointerToBase.size()); - for (auto Pair : PointerToBase) { - Temp.push_back(Pair.first); - } - std::sort(Temp.begin(), Temp.end(), order_by_name); - for (Value *Ptr : Temp) { - Value *Base = PointerToBase[Ptr]; + for (auto &Pair : PointerToBase) { errs() << " derived "; - Ptr->printAsOperand(errs(), false); + Pair.first->printAsOperand(errs(), false); errs() << " base "; - Base->printAsOperand(errs(), false); + Pair.second->printAsOperand(errs(), false); errs() << "\n";; } } @@ -1194,7 +1059,7 @@ static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache, /// Given an updated version of the dataflow liveness results, update the /// liveset and base pointer maps for the call site CS. static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, - const CallSite &CS, + CallSite CS, PartiallyConstructedSafepointRecord &result); static void recomputeLiveInValues( @@ -1206,8 +1071,7 @@ static void recomputeLiveInValues( computeLiveInValues(DT, F, RevisedLivenessData); for (size_t i = 0; i < records.size(); i++) { struct PartiallyConstructedSafepointRecord &info = records[i]; - const CallSite &CS = toUpdate[i]; - recomputeLiveInValues(RevisedLivenessData, CS, info); + recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info); } } @@ -1257,8 +1121,7 @@ static AttributeSet legalizeCallAttributes(AttributeSet AS) { // These attributes control the generation of the gc.statepoint call / // invoke itself; and once the gc.statepoint is in place, they're of no // use. - if (Attr.hasAttribute("statepoint-num-patch-bytes") || - Attr.hasAttribute("statepoint-id")) + if (isStatepointDirectiveAttr(Attr)) continue; Ret = Ret.addAttributes( @@ -1349,11 +1212,37 @@ namespace { class DeferredReplacement { AssertingVH<Instruction> Old; AssertingVH<Instruction> New; + bool IsDeoptimize = false; + + DeferredReplacement() {} public: - explicit DeferredReplacement(Instruction *Old, Instruction *New) : - Old(Old), New(New) { - assert(Old != New && "Not allowed!"); + static DeferredReplacement createRAUW(Instruction *Old, Instruction *New) { + assert(Old != New && Old && New && + "Cannot RAUW equal values or to / from null!"); + + DeferredReplacement D; + D.Old = Old; + D.New = New; + return D; + } + + static DeferredReplacement createDelete(Instruction *ToErase) { + DeferredReplacement D; + D.Old = ToErase; + return D; + } + + static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) { +#ifndef NDEBUG + auto *F = cast<CallInst>(Old)->getCalledFunction(); + assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize && + "Only way to construct a deoptimize deferred replacement"); +#endif + DeferredReplacement D; + D.Old = Old; + D.IsDeoptimize = true; + return D; } /// Does the task represented by this instance. @@ -1362,12 +1251,23 @@ public: Instruction *NewI = New; assert(OldI != NewI && "Disallowed at construction?!"); + assert((!IsDeoptimize || !New) && + "Deoptimize instrinsics are not replaced!"); Old = nullptr; New = nullptr; if (NewI) OldI->replaceAllUsesWith(NewI); + + if (IsDeoptimize) { + // Note: we've inserted instructions, so the call to llvm.deoptimize may + // not necessarilly be followed by the matching return. + auto *RI = cast<ReturnInst>(OldI->getParent()->getTerminator()); + new UnreachableInst(RI->getContext(), RI); + RI->eraseFromParent(); + } + OldI->eraseFromParent(); } }; @@ -1380,8 +1280,6 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */ PartiallyConstructedSafepointRecord &Result, std::vector<DeferredReplacement> &Replacements) { assert(BasePtrs.size() == LiveVariables.size()); - assert((UseDeoptBundles || isStatepoint(CS)) && - "This method expects to be rewriting a statepoint"); // Then go ahead and use the builder do actually do the inserts. We insert // immediately before the previous instruction under the assumption that all @@ -1391,47 +1289,53 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */ IRBuilder<> Builder(InsertBefore); ArrayRef<Value *> GCArgs(LiveVariables); - uint64_t StatepointID = 0xABCDEF00; + uint64_t StatepointID = StatepointDirectives::DefaultStatepointID; uint32_t NumPatchBytes = 0; uint32_t Flags = uint32_t(StatepointFlags::None); - ArrayRef<Use> CallArgs; - ArrayRef<Use> DeoptArgs; + ArrayRef<Use> CallArgs(CS.arg_begin(), CS.arg_end()); + ArrayRef<Use> DeoptArgs = GetDeoptBundleOperands(CS); ArrayRef<Use> TransitionArgs; - - Value *CallTarget = nullptr; - - if (UseDeoptBundles) { - CallArgs = {CS.arg_begin(), CS.arg_end()}; - DeoptArgs = GetDeoptBundleOperands(CS); - // TODO: we don't fill in TransitionArgs or Flags in this branch, but we - // could have an operand bundle for that too. - AttributeSet OriginalAttrs = CS.getAttributes(); - - Attribute AttrID = OriginalAttrs.getAttribute(AttributeSet::FunctionIndex, - "statepoint-id"); - if (AttrID.isStringAttribute()) - AttrID.getValueAsString().getAsInteger(10, StatepointID); - - Attribute AttrNumPatchBytes = OriginalAttrs.getAttribute( - AttributeSet::FunctionIndex, "statepoint-num-patch-bytes"); - if (AttrNumPatchBytes.isStringAttribute()) - AttrNumPatchBytes.getValueAsString().getAsInteger(10, NumPatchBytes); - - CallTarget = CS.getCalledValue(); - } else { - // This branch will be gone soon, and we will soon only support the - // UseDeoptBundles == true configuration. - Statepoint OldSP(CS); - StatepointID = OldSP.getID(); - NumPatchBytes = OldSP.getNumPatchBytes(); - Flags = OldSP.getFlags(); - - CallArgs = {OldSP.arg_begin(), OldSP.arg_end()}; - DeoptArgs = {OldSP.vm_state_begin(), OldSP.vm_state_end()}; - TransitionArgs = {OldSP.gc_transition_args_begin(), - OldSP.gc_transition_args_end()}; - CallTarget = OldSP.getCalledValue(); + if (auto TransitionBundle = + CS.getOperandBundle(LLVMContext::OB_gc_transition)) { + Flags |= uint32_t(StatepointFlags::GCTransition); + TransitionArgs = TransitionBundle->Inputs; + } + + // Instead of lowering calls to @llvm.experimental.deoptimize as normal calls + // with a return value, we lower then as never returning calls to + // __llvm_deoptimize that are followed by unreachable to get better codegen. + bool IsDeoptimize = false; + + StatepointDirectives SD = + parseStatepointDirectivesFromAttrs(CS.getAttributes()); + if (SD.NumPatchBytes) + NumPatchBytes = *SD.NumPatchBytes; + if (SD.StatepointID) + StatepointID = *SD.StatepointID; + + Value *CallTarget = CS.getCalledValue(); + if (Function *F = dyn_cast<Function>(CallTarget)) { + if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize) { + // Calls to llvm.experimental.deoptimize are lowered to calls to the + // __llvm_deoptimize symbol. We want to resolve this now, since the + // verifier does not allow taking the address of an intrinsic function. + + SmallVector<Type *, 8> DomainTy; + for (Value *Arg : CallArgs) + DomainTy.push_back(Arg->getType()); + auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy, + /* isVarArg = */ false); + + // Note: CallTarget can be a bitcast instruction of a symbol if there are + // calls to @llvm.experimental.deoptimize with different argument types in + // the same module. This is fine -- we assume the frontend knew what it + // was doing when generating this kind of IR. + CallTarget = + F->getParent()->getOrInsertFunction("__llvm_deoptimize", FTy); + + IsDeoptimize = true; + } } // Create the statepoint given all the arguments @@ -1514,7 +1418,13 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */ } assert(Token && "Should be set in one of the above branches!"); - if (UseDeoptBundles) { + if (IsDeoptimize) { + // If we're wrapping an @llvm.experimental.deoptimize in a statepoint, we + // transform the tail-call like structure to a call to a void function + // followed by unreachable to get better codegen. + Replacements.push_back( + DeferredReplacement::createDeoptimizeReplacement(CS.getInstruction())); + } else { Token->setName("statepoint_token"); if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) { StringRef Name = @@ -1528,24 +1438,12 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */ // llvm::Instruction. Instead, we defer the replacement and deletion to // after the live sets have been made explicit in the IR, and we no longer // have raw pointers to worry about. - Replacements.emplace_back(CS.getInstruction(), GCResult); + Replacements.emplace_back( + DeferredReplacement::createRAUW(CS.getInstruction(), GCResult)); } else { - Replacements.emplace_back(CS.getInstruction(), nullptr); + Replacements.emplace_back( + DeferredReplacement::createDelete(CS.getInstruction())); } - } else { - assert(!CS.getInstruction()->hasNUsesOrMore(2) && - "only valid use before rewrite is gc.result"); - assert(!CS.getInstruction()->hasOneUse() || - isGCResult(cast<Instruction>(*CS.getInstruction()->user_begin()))); - - // Take the name of the original statepoint token if there was one. - Token->takeName(CS.getInstruction()); - - // Update the gc.result of the original statepoint (if any) to use the newly - // inserted statepoint. This is safe to do here since the token can't be - // considered a live reference. - CS.getInstruction()->replaceAllUsesWith(Token); - CS.getInstruction()->eraseFromParent(); } Result.StatepointToken = Token; @@ -1555,43 +1453,13 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */ CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder); } -namespace { -struct NameOrdering { - Value *Base; - Value *Derived; - - bool operator()(NameOrdering const &a, NameOrdering const &b) { - return -1 == a.Derived->getName().compare(b.Derived->getName()); - } -}; -} - -static void StabilizeOrder(SmallVectorImpl<Value *> &BaseVec, - SmallVectorImpl<Value *> &LiveVec) { - assert(BaseVec.size() == LiveVec.size()); - - SmallVector<NameOrdering, 64> Temp; - for (size_t i = 0; i < BaseVec.size(); i++) { - NameOrdering v; - v.Base = BaseVec[i]; - v.Derived = LiveVec[i]; - Temp.push_back(v); - } - - std::sort(Temp.begin(), Temp.end(), NameOrdering()); - for (size_t i = 0; i < BaseVec.size(); i++) { - BaseVec[i] = Temp[i].Base; - LiveVec[i] = Temp[i].Derived; - } -} - // Replace an existing gc.statepoint with a new one and a set of gc.relocates // which make the relocations happening at this safepoint explicit. // // WARNING: Does not do any fixup to adjust users of the original live // values. That's the callers responsibility. static void -makeStatepointExplicit(DominatorTree &DT, const CallSite &CS, +makeStatepointExplicit(DominatorTree &DT, CallSite CS, PartiallyConstructedSafepointRecord &Result, std::vector<DeferredReplacement> &Replacements) { const auto &LiveSet = Result.LiveSet; @@ -1609,11 +1477,6 @@ makeStatepointExplicit(DominatorTree &DT, const CallSite &CS, } assert(LiveVec.size() == BaseVec.size()); - // To make the output IR slightly more stable (for use in diffs), ensure a - // fixed order of the values in the safepoint (by sorting the value name). - // The order is otherwise meaningless. - StabilizeOrder(BaseVec, LiveVec); - // Do the actual rewriting and delete the old statepoint makeStatepointExplicitImpl(CS, BaseVec, LiveVec, Result, Replacements); } @@ -1634,7 +1497,7 @@ insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs, if (!Relocate) continue; - Value *OriginalValue = const_cast<Value *>(Relocate->getDerivedPtr()); + Value *OriginalValue = Relocate->getDerivedPtr(); assert(AllocaMap.count(OriginalValue)); Value *Alloca = AllocaMap[OriginalValue]; @@ -1660,11 +1523,10 @@ insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs, // Helper function for the "relocationViaAlloca". Similar to the // "insertRelocationStores" but works for rematerialized values. -static void -insertRematerializationStores( - RematerializedValueMapTy RematerializedValues, - DenseMap<Value *, Value *> &AllocaMap, - DenseSet<Value *> &VisitedLiveValues) { +static void insertRematerializationStores( + const RematerializedValueMapTy &RematerializedValues, + DenseMap<Value *, Value *> &AllocaMap, + DenseSet<Value *> &VisitedLiveValues) { for (auto RematerializedValuePair: RematerializedValues) { Instruction *RematerializedValue = RematerializedValuePair.first; @@ -1691,9 +1553,8 @@ static void relocationViaAlloca( // record initial number of (static) allocas; we'll check we have the same // number when we get done. int InitialAllocaNum = 0; - for (auto I = F.getEntryBlock().begin(), E = F.getEntryBlock().end(); I != E; - I++) - if (isa<AllocaInst>(*I)) + for (Instruction &I : F.getEntryBlock()) + if (isa<AllocaInst>(I)) InitialAllocaNum++; #endif @@ -1777,8 +1638,7 @@ static void relocationViaAlloca( auto InsertClobbersAt = [&](Instruction *IP) { for (auto *AI : ToClobber) { - auto AIType = cast<PointerType>(AI->getType()); - auto PT = cast<PointerType>(AIType->getElementType()); + auto PT = cast<PointerType>(AI->getAllocatedType()); Constant *CPN = ConstantPointerNull::get(PT); StoreInst *Store = new StoreInst(CPN, AI); Store->insertBefore(IP); @@ -1919,141 +1779,7 @@ static void findLiveReferences( computeLiveInValues(DT, F, OriginalLivenessData); for (size_t i = 0; i < records.size(); i++) { struct PartiallyConstructedSafepointRecord &info = records[i]; - const CallSite &CS = toUpdate[i]; - analyzeParsePointLiveness(DT, OriginalLivenessData, CS, info); - } -} - -/// Remove any vector of pointers from the live set by scalarizing them over the -/// statepoint instruction. Adds the scalarized pieces to the live set. It -/// would be preferable to include the vector in the statepoint itself, but -/// the lowering code currently does not handle that. Extending it would be -/// slightly non-trivial since it requires a format change. Given how rare -/// such cases are (for the moment?) scalarizing is an acceptable compromise. -static void splitVectorValues(Instruction *StatepointInst, - StatepointLiveSetTy &LiveSet, - DenseMap<Value *, Value *>& PointerToBase, - DominatorTree &DT) { - SmallVector<Value *, 16> ToSplit; - for (Value *V : LiveSet) - if (isa<VectorType>(V->getType())) - ToSplit.push_back(V); - - if (ToSplit.empty()) - return; - - DenseMap<Value *, SmallVector<Value *, 16>> ElementMapping; - - Function &F = *(StatepointInst->getParent()->getParent()); - - DenseMap<Value *, AllocaInst *> AllocaMap; - // First is normal return, second is exceptional return (invoke only) - DenseMap<Value *, std::pair<Value *, Value *>> Replacements; - for (Value *V : ToSplit) { - AllocaInst *Alloca = - new AllocaInst(V->getType(), "", F.getEntryBlock().getFirstNonPHI()); - AllocaMap[V] = Alloca; - - VectorType *VT = cast<VectorType>(V->getType()); - IRBuilder<> Builder(StatepointInst); - SmallVector<Value *, 16> Elements; - for (unsigned i = 0; i < VT->getNumElements(); i++) - Elements.push_back(Builder.CreateExtractElement(V, Builder.getInt32(i))); - ElementMapping[V] = Elements; - - auto InsertVectorReform = [&](Instruction *IP) { - Builder.SetInsertPoint(IP); - Builder.SetCurrentDebugLocation(IP->getDebugLoc()); - Value *ResultVec = UndefValue::get(VT); - for (unsigned i = 0; i < VT->getNumElements(); i++) - ResultVec = Builder.CreateInsertElement(ResultVec, Elements[i], - Builder.getInt32(i)); - return ResultVec; - }; - - if (isa<CallInst>(StatepointInst)) { - BasicBlock::iterator Next(StatepointInst); - Next++; - Instruction *IP = &*(Next); - Replacements[V].first = InsertVectorReform(IP); - Replacements[V].second = nullptr; - } else { - InvokeInst *Invoke = cast<InvokeInst>(StatepointInst); - // We've already normalized - check that we don't have shared destination - // blocks - BasicBlock *NormalDest = Invoke->getNormalDest(); - assert(!isa<PHINode>(NormalDest->begin())); - BasicBlock *UnwindDest = Invoke->getUnwindDest(); - assert(!isa<PHINode>(UnwindDest->begin())); - // Insert insert element sequences in both successors - Instruction *IP = &*(NormalDest->getFirstInsertionPt()); - Replacements[V].first = InsertVectorReform(IP); - IP = &*(UnwindDest->getFirstInsertionPt()); - Replacements[V].second = InsertVectorReform(IP); - } - } - - for (Value *V : ToSplit) { - AllocaInst *Alloca = AllocaMap[V]; - - // Capture all users before we start mutating use lists - SmallVector<Instruction *, 16> Users; - for (User *U : V->users()) - Users.push_back(cast<Instruction>(U)); - - for (Instruction *I : Users) { - if (auto Phi = dyn_cast<PHINode>(I)) { - for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) - if (V == Phi->getIncomingValue(i)) { - LoadInst *Load = new LoadInst( - Alloca, "", Phi->getIncomingBlock(i)->getTerminator()); - Phi->setIncomingValue(i, Load); - } - } else { - LoadInst *Load = new LoadInst(Alloca, "", I); - I->replaceUsesOfWith(V, Load); - } - } - - // Store the original value and the replacement value into the alloca - StoreInst *Store = new StoreInst(V, Alloca); - if (auto I = dyn_cast<Instruction>(V)) - Store->insertAfter(I); - else - Store->insertAfter(Alloca); - - // Normal return for invoke, or call return - Instruction *Replacement = cast<Instruction>(Replacements[V].first); - (new StoreInst(Replacement, Alloca))->insertAfter(Replacement); - // Unwind return for invoke only - Replacement = cast_or_null<Instruction>(Replacements[V].second); - if (Replacement) - (new StoreInst(Replacement, Alloca))->insertAfter(Replacement); - } - - // apply mem2reg to promote alloca to SSA - SmallVector<AllocaInst *, 16> Allocas; - for (Value *V : ToSplit) - Allocas.push_back(AllocaMap[V]); - PromoteMemToReg(Allocas, DT); - - // Update our tracking of live pointers and base mappings to account for the - // changes we just made. - for (Value *V : ToSplit) { - auto &Elements = ElementMapping[V]; - - LiveSet.erase(V); - LiveSet.insert(Elements.begin(), Elements.end()); - // We need to update the base mapping as well. - assert(PointerToBase.count(V)); - Value *OldBase = PointerToBase[V]; - auto &BaseElements = ElementMapping[OldBase]; - PointerToBase.erase(V); - assert(Elements.size() == BaseElements.size()); - for (unsigned i = 0; i < Elements.size(); i++) { - Value *Elem = Elements[i]; - PointerToBase[Elem] = BaseElements[i]; - } + analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info); } } @@ -2109,7 +1835,7 @@ chainToBasePointerCost(SmallVectorImpl<Instruction*> &Chain, } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) { // Cost of the address calculation - Type *ValTy = GEP->getPointerOperandType()->getPointerElementType(); + Type *ValTy = GEP->getSourceElementType(); Cost += TTI.getAddressComputationCost(ValTy); // And cost of the GEP itself @@ -2244,7 +1970,7 @@ static void rematerializeLiveValues(CallSite CS, // Remove rematerializaed values from the live set for (auto LiveValue: LiveValuesToBeDeleted) { - Info.LiveSet.erase(LiveValue); + Info.LiveSet.remove(LiveValue); } } @@ -2257,11 +1983,8 @@ static bool insertParsePoints(Function &F, DominatorTree &DT, Uniqued.insert(ToUpdate.begin(), ToUpdate.end()); assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!"); - for (CallSite CS : ToUpdate) { - assert(CS.getInstruction()->getParent()->getParent() == &F); - assert((UseDeoptBundles || isStatepoint(CS)) && - "expected to already be a deopt statepoint"); - } + for (CallSite CS : ToUpdate) + assert(CS.getInstruction()->getFunction() == &F); #endif // When inserting gc.relocates for invokes, we need to be able to insert at @@ -2287,12 +2010,7 @@ static bool insertParsePoints(Function &F, DominatorTree &DT, for (CallSite CS : ToUpdate) { SmallVector<Value *, 64> DeoptValues; - iterator_range<const Use *> DeoptStateRange = - UseDeoptBundles - ? iterator_range<const Use *>(GetDeoptBundleOperands(CS)) - : iterator_range<const Use *>(Statepoint(CS).vm_state_args()); - - for (Value *Arg : DeoptStateRange) { + for (Value *Arg : GetDeoptBundleOperands(CS)) { assert(!isUnhandledGCPointerType(Arg->getType()) && "support for FCA unimplemented"); if (isHandledGCPointerType(Arg->getType())) @@ -2374,29 +2092,13 @@ static bool insertParsePoints(Function &F, DominatorTree &DT, for (auto &Info : Records) for (auto &BasePair : Info.PointerToBase) if (isa<Constant>(BasePair.second)) - Info.LiveSet.erase(BasePair.first); + Info.LiveSet.remove(BasePair.first); for (CallInst *CI : Holders) CI->eraseFromParent(); Holders.clear(); - // Do a limited scalarization of any live at safepoint vector values which - // contain pointers. This enables this pass to run after vectorization at - // the cost of some possible performance loss. Note: This is known to not - // handle updating of the side tables correctly which can lead to relocation - // bugs when the same vector is live at multiple statepoints. We're in the - // process of implementing the alternate lowering - relocating the - // vector-of-pointers as first class item and updating the backend to - // understand that - but that's not yet complete. - if (UseVectorSplit) - for (size_t i = 0; i < Records.size(); i++) { - PartiallyConstructedSafepointRecord &Info = Records[i]; - Instruction *Statepoint = ToUpdate[i].getInstruction(); - splitVectorValues(cast<Instruction>(Statepoint), Info.LiveSet, - Info.PointerToBase, DT); - } - // In order to reduce live set of statepoint we might choose to rematerialize // some values instead of relocating them. This is purely an optimization and // does not influence correctness. @@ -2592,13 +2294,9 @@ bool RewriteStatepointsForGC::runOnFunction(Function &F) { getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); auto NeedsRewrite = [](Instruction &I) { - if (UseDeoptBundles) { - if (ImmutableCallSite CS = ImmutableCallSite(&I)) - return !callsGCLeafFunction(CS); - return false; - } - - return isStatepoint(I); + if (ImmutableCallSite CS = ImmutableCallSite(&I)) + return !callsGCLeafFunction(CS) && !isStatepoint(CS); + return false; }; // Gather all the statepoints which need rewritten. Be careful to only @@ -2682,15 +2380,12 @@ bool RewriteStatepointsForGC::runOnFunction(Function &F) { /// Compute the live-in set for the location rbegin starting from /// the live-out set of the basic block -static void computeLiveInValues(BasicBlock::reverse_iterator rbegin, - BasicBlock::reverse_iterator rend, - DenseSet<Value *> &LiveTmp) { - - for (BasicBlock::reverse_iterator ritr = rbegin; ritr != rend; ritr++) { - Instruction *I = &*ritr; - +static void computeLiveInValues(BasicBlock::reverse_iterator Begin, + BasicBlock::reverse_iterator End, + SetVector<Value *> &LiveTmp) { + for (auto &I : make_range(Begin, End)) { // KILL/Def - Remove this definition from LiveIn - LiveTmp.erase(I); + LiveTmp.remove(&I); // Don't consider *uses* in PHI nodes, we handle their contribution to // predecessor blocks when we seed the LiveOut sets @@ -2698,7 +2393,7 @@ static void computeLiveInValues(BasicBlock::reverse_iterator rbegin, continue; // USE - Add to the LiveIn set for this instruction - for (Value *V : I->operands()) { + for (Value *V : I.operands()) { assert(!isUnhandledGCPointerType(V->getType()) && "support for FCA unimplemented"); if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) { @@ -2718,24 +2413,24 @@ static void computeLiveInValues(BasicBlock::reverse_iterator rbegin, } } -static void computeLiveOutSeed(BasicBlock *BB, DenseSet<Value *> &LiveTmp) { - +static void computeLiveOutSeed(BasicBlock *BB, SetVector<Value *> &LiveTmp) { for (BasicBlock *Succ : successors(BB)) { - const BasicBlock::iterator E(Succ->getFirstNonPHI()); - for (BasicBlock::iterator I = Succ->begin(); I != E; I++) { - PHINode *Phi = cast<PHINode>(&*I); - Value *V = Phi->getIncomingValueForBlock(BB); + for (auto &I : *Succ) { + PHINode *PN = dyn_cast<PHINode>(&I); + if (!PN) + break; + + Value *V = PN->getIncomingValueForBlock(BB); assert(!isUnhandledGCPointerType(V->getType()) && "support for FCA unimplemented"); - if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) { + if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) LiveTmp.insert(V); - } } } } -static DenseSet<Value *> computeKillSet(BasicBlock *BB) { - DenseSet<Value *> KillSet; +static SetVector<Value *> computeKillSet(BasicBlock *BB) { + SetVector<Value *> KillSet; for (Instruction &I : *BB) if (isHandledGCPointerType(I.getType())) KillSet.insert(&I); @@ -2745,7 +2440,7 @@ static DenseSet<Value *> computeKillSet(BasicBlock *BB) { #ifndef NDEBUG /// Check that the items in 'Live' dominate 'TI'. This is used as a basic /// sanity check for the liveness computation. -static void checkBasicSSA(DominatorTree &DT, DenseSet<Value *> &Live, +static void checkBasicSSA(DominatorTree &DT, SetVector<Value *> &Live, TerminatorInst *TI, bool TermOkay = false) { for (Value *V : Live) { if (auto *I = dyn_cast<Instruction>(V)) { @@ -2773,17 +2468,7 @@ static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data, static void computeLiveInValues(DominatorTree &DT, Function &F, GCPtrLivenessData &Data) { - - SmallSetVector<BasicBlock *, 200> Worklist; - auto AddPredsToWorklist = [&](BasicBlock *BB) { - // We use a SetVector so that we don't have duplicates in the worklist. - Worklist.insert(pred_begin(BB), pred_end(BB)); - }; - auto NextItem = [&]() { - BasicBlock *BB = Worklist.back(); - Worklist.pop_back(); - return BB; - }; + SmallSetVector<BasicBlock *, 32> Worklist; // Seed the liveness for each individual block for (BasicBlock &BB : F) { @@ -2796,56 +2481,55 @@ static void computeLiveInValues(DominatorTree &DT, Function &F, assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill"); #endif - Data.LiveOut[&BB] = DenseSet<Value *>(); + Data.LiveOut[&BB] = SetVector<Value *>(); computeLiveOutSeed(&BB, Data.LiveOut[&BB]); Data.LiveIn[&BB] = Data.LiveSet[&BB]; - set_union(Data.LiveIn[&BB], Data.LiveOut[&BB]); - set_subtract(Data.LiveIn[&BB], Data.KillSet[&BB]); + Data.LiveIn[&BB].set_union(Data.LiveOut[&BB]); + Data.LiveIn[&BB].set_subtract(Data.KillSet[&BB]); if (!Data.LiveIn[&BB].empty()) - AddPredsToWorklist(&BB); + Worklist.insert(pred_begin(&BB), pred_end(&BB)); } // Propagate that liveness until stable while (!Worklist.empty()) { - BasicBlock *BB = NextItem(); + BasicBlock *BB = Worklist.pop_back_val(); - // Compute our new liveout set, then exit early if it hasn't changed - // despite the contribution of our successor. - DenseSet<Value *> LiveOut = Data.LiveOut[BB]; + // Compute our new liveout set, then exit early if it hasn't changed despite + // the contribution of our successor. + SetVector<Value *> LiveOut = Data.LiveOut[BB]; const auto OldLiveOutSize = LiveOut.size(); for (BasicBlock *Succ : successors(BB)) { assert(Data.LiveIn.count(Succ)); - set_union(LiveOut, Data.LiveIn[Succ]); + LiveOut.set_union(Data.LiveIn[Succ]); } // assert OutLiveOut is a subset of LiveOut if (OldLiveOutSize == LiveOut.size()) { // If the sets are the same size, then we didn't actually add anything - // when unioning our successors LiveIn Thus, the LiveIn of this block + // when unioning our successors LiveIn. Thus, the LiveIn of this block // hasn't changed. continue; } Data.LiveOut[BB] = LiveOut; // Apply the effects of this basic block - DenseSet<Value *> LiveTmp = LiveOut; - set_union(LiveTmp, Data.LiveSet[BB]); - set_subtract(LiveTmp, Data.KillSet[BB]); + SetVector<Value *> LiveTmp = LiveOut; + LiveTmp.set_union(Data.LiveSet[BB]); + LiveTmp.set_subtract(Data.KillSet[BB]); assert(Data.LiveIn.count(BB)); - const DenseSet<Value *> &OldLiveIn = Data.LiveIn[BB]; + const SetVector<Value *> &OldLiveIn = Data.LiveIn[BB]; // assert: OldLiveIn is a subset of LiveTmp if (OldLiveIn.size() != LiveTmp.size()) { Data.LiveIn[BB] = LiveTmp; - AddPredsToWorklist(BB); + Worklist.insert(pred_begin(BB), pred_end(BB)); } - } // while( !worklist.empty() ) + } // while (!Worklist.empty()) #ifndef NDEBUG // Sanity check our output against SSA properties. This helps catch any // missing kills during the above iteration. - for (BasicBlock &BB : F) { + for (BasicBlock &BB : F) checkBasicSSA(DT, Data, BB); - } #endif } @@ -2856,7 +2540,7 @@ static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data, // Note: The copy is intentional and required assert(Data.LiveOut.count(BB)); - DenseSet<Value *> LiveOut = Data.LiveOut[BB]; + SetVector<Value *> LiveOut = Data.LiveOut[BB]; // We want to handle the statepoint itself oddly. It's // call result is not live (normal), nor are it's arguments @@ -2864,12 +2548,12 @@ static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data, // specifically what we need to relocate BasicBlock::reverse_iterator rend(Inst->getIterator()); computeLiveInValues(BB->rbegin(), rend, LiveOut); - LiveOut.erase(Inst); + LiveOut.remove(Inst); Out.insert(LiveOut.begin(), LiveOut.end()); } static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, - const CallSite &CS, + CallSite CS, PartiallyConstructedSafepointRecord &Info) { Instruction *Inst = CS.getInstruction(); StatepointLiveSetTy Updated; @@ -2877,33 +2561,32 @@ static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, #ifndef NDEBUG DenseSet<Value *> Bases; - for (auto KVPair : Info.PointerToBase) { + for (auto KVPair : Info.PointerToBase) Bases.insert(KVPair.second); - } #endif + // We may have base pointers which are now live that weren't before. We need // to update the PointerToBase structure to reflect this. for (auto V : Updated) - if (!Info.PointerToBase.count(V)) { - assert(Bases.count(V) && "can't find base for unexpected live value"); - Info.PointerToBase[V] = V; + if (Info.PointerToBase.insert({V, V}).second) { + assert(Bases.count(V) && "Can't find base for unexpected live value!"); continue; } #ifndef NDEBUG - for (auto V : Updated) { + for (auto V : Updated) assert(Info.PointerToBase.count(V) && - "must be able to find base for live value"); - } + "Must be able to find base for live value!"); #endif // Remove any stale base mappings - this can happen since our liveness is - // more precise then the one inherent in the base pointer analysis + // more precise then the one inherent in the base pointer analysis. DenseSet<Value *> ToErase; for (auto KVPair : Info.PointerToBase) if (!Updated.count(KVPair.first)) ToErase.insert(KVPair.first); - for (auto V : ToErase) + + for (auto *V : ToErase) Info.PointerToBase.erase(V); #ifndef NDEBUG |