Index: llvm/trunk/include/llvm/ADT/SetVector.h =================================================================== --- llvm/trunk/include/llvm/ADT/SetVector.h +++ llvm/trunk/include/llvm/ADT/SetVector.h @@ -225,6 +225,31 @@ bool operator!=(const SetVector &that) const { return vector_ != that.vector_; } + + /// \brief Compute This := This u S, return whether 'This' changed. + /// TODO: We should be able to use set_union from SetOperations.h, but + /// SetVector interface is inconsistent with DenseSet. + template + bool set_union(const STy &S) { + bool Changed = false; + + for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; + ++SI) + if (insert(*SI)) + Changed = true; + + return Changed; + } + + /// \brief Compute This := This - B + /// TODO: We should be able to use set_subtract from SetOperations.h, but + /// SetVector interface is inconsistent with DenseSet. + template + void set_subtract(const STy &S) { + for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; + ++SI) + remove(*SI); + } private: /// \brief A wrapper predicate designed for use with std::remove_if. Index: llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -137,18 +137,18 @@ namespace { struct GCPtrLivenessData { /// Values defined in this block. - DenseMap> KillSet; + MapVector> KillSet; /// Values used in this block (and thus live); does not included values /// killed within this block. - DenseMap> LiveSet; + MapVector> LiveSet; /// Values live into this basic block (i.e. used by any /// instruction in this basic block or ones reachable from here) - DenseMap> LiveIn; + MapVector> LiveIn; /// Values live out of this basic block (i.e. live into /// any successor block) - DenseMap> LiveOut; + MapVector> LiveOut; }; // The type of the internal cache used inside the findBasePointers family @@ -161,9 +161,9 @@ // 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 DefiningValueMapTy; -typedef DenseSet StatepointLiveSetTy; -typedef DenseMap, AssertingVH> +typedef MapVector DefiningValueMapTy; +typedef SetVector StatepointLiveSetTy; +typedef MapVector, AssertingVH> RematerializedValueMapTy; struct PartiallyConstructedSafepointRecord { @@ -171,7 +171,7 @@ StatepointLiveSetTy LiveSet; /// Mapping from live pointers to a base-defining-value - DenseMap PointerToBase; + MapVector PointerToBase; /// The *new* gc.statepoint instruction itself. This produces the token /// that normal path gc.relocates and the gc.result are tied to. @@ -262,19 +262,6 @@ } #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, @@ -295,14 +282,8 @@ 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 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) + for (Value *V : LiveSet) dbgs() << " " << V->getName() << " " << *V << "\n"; } if (PrintLiveSetSize) { @@ -1063,15 +1044,9 @@ // pointer was a base pointer. static void findBasePointers(const StatepointLiveSetTy &live, - DenseMap &PointerToBase, + MapVector &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 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; @@ -1095,25 +1070,16 @@ static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache, const CallSite &CS, PartiallyConstructedSafepointRecord &result) { - DenseMap PointerToBase; + MapVector 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 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";; } } @@ -1519,32 +1485,6 @@ CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder); } -static void StabilizeOrder(SmallVectorImpl &BaseVec, - SmallVectorImpl &LiveVec) { - assert(BaseVec.size() == LiveVec.size()); - - struct BaseDerivedPair { - Value *Base; - Value *Derived; - }; - - SmallVector NameOrdering; - NameOrdering.reserve(BaseVec.size()); - - for (size_t i = 0, e = BaseVec.size(); i < e; i++) - NameOrdering.push_back({BaseVec[i], LiveVec[i]}); - - std::sort(NameOrdering.begin(), NameOrdering.end(), - [](const BaseDerivedPair &L, const BaseDerivedPair &R) { - return L.Derived->getName() < R.Derived->getName(); - }); - - for (size_t i = 0; i < BaseVec.size(); i++) { - BaseVec[i] = NameOrdering[i].Base; - LiveVec[i] = NameOrdering[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. // @@ -1569,11 +1509,6 @@ } 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); } @@ -2069,7 +2004,7 @@ // Remove rematerializaed values from the live set for (auto LiveValue: LiveValuesToBeDeleted) { - Info.LiveSet.erase(LiveValue); + Info.LiveSet.remove(LiveValue); } } @@ -2191,7 +2126,7 @@ for (auto &Info : Records) for (auto &BasePair : Info.PointerToBase) if (isa(BasePair.second)) - Info.LiveSet.erase(BasePair.first); + Info.LiveSet.remove(BasePair.first); for (CallInst *CI : Holders) CI->eraseFromParent(); @@ -2481,13 +2416,13 @@ /// the live-out set of the basic block static void computeLiveInValues(BasicBlock::reverse_iterator rbegin, BasicBlock::reverse_iterator rend, - DenseSet &LiveTmp) { + SetVector &LiveTmp) { for (BasicBlock::reverse_iterator ritr = rbegin; ritr != rend; ritr++) { Instruction *I = &*ritr; // 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 @@ -2515,7 +2450,7 @@ } } -static void computeLiveOutSeed(BasicBlock *BB, DenseSet &LiveTmp) { +static void computeLiveOutSeed(BasicBlock *BB, SetVector &LiveTmp) { for (BasicBlock *Succ : successors(BB)) { const BasicBlock::iterator E(Succ->getFirstNonPHI()); @@ -2531,8 +2466,8 @@ } } -static DenseSet computeKillSet(BasicBlock *BB) { - DenseSet KillSet; +static SetVector computeKillSet(BasicBlock *BB) { + SetVector KillSet; for (Instruction &I : *BB) if (isHandledGCPointerType(I.getType())) KillSet.insert(&I); @@ -2542,7 +2477,7 @@ #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 &Live, +static void checkBasicSSA(DominatorTree &DT, SetVector &Live, TerminatorInst *TI, bool TermOkay = false) { for (Value *V : Live) { if (auto *I = dyn_cast(V)) { @@ -2593,11 +2528,11 @@ assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill"); #endif - Data.LiveOut[&BB] = DenseSet(); + Data.LiveOut[&BB] = SetVector(); 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); } @@ -2608,11 +2543,11 @@ // Compute our new liveout set, then exit early if it hasn't changed // despite the contribution of our successor. - DenseSet LiveOut = Data.LiveOut[BB]; + SetVector 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()) { @@ -2624,12 +2559,12 @@ Data.LiveOut[BB] = LiveOut; // Apply the effects of this basic block - DenseSet LiveTmp = LiveOut; - set_union(LiveTmp, Data.LiveSet[BB]); - set_subtract(LiveTmp, Data.KillSet[BB]); + SetVector LiveTmp = LiveOut; + LiveTmp.set_union(Data.LiveSet[BB]); + LiveTmp.set_subtract(Data.KillSet[BB]); assert(Data.LiveIn.count(BB)); - const DenseSet &OldLiveIn = Data.LiveIn[BB]; + const SetVector &OldLiveIn = Data.LiveIn[BB]; // assert: OldLiveIn is a subset of LiveTmp if (OldLiveIn.size() != LiveTmp.size()) { Data.LiveIn[BB] = LiveTmp; @@ -2653,7 +2588,7 @@ // Note: The copy is intentional and required assert(Data.LiveOut.count(BB)); - DenseSet LiveOut = Data.LiveOut[BB]; + SetVector 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 @@ -2661,7 +2596,7 @@ // 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()); } Index: llvm/trunk/test/Transforms/RewriteStatepointsForGC/base-vector.ll =================================================================== --- llvm/trunk/test/Transforms/RewriteStatepointsForGC/base-vector.ll +++ llvm/trunk/test/Transforms/RewriteStatepointsForGC/base-vector.ll @@ -7,9 +7,9 @@ ; CHECK: extractelement ; CHECK: statepoint ; CHECK: gc.relocate -; CHECK-DAG: ; (%base_ee, %base_ee) -; CHECK: gc.relocate ; CHECK-DAG: ; (%base_ee, %obj) +; CHECK: gc.relocate +; CHECK-DAG: ; (%base_ee, %base_ee) ; Note that the second extractelement is actually redundant here. A correct output would ; be to reuse the existing obj as a base since it is actually a base pointer. entry: Index: llvm/trunk/test/Transforms/RewriteStatepointsForGC/basics.ll =================================================================== --- llvm/trunk/test/Transforms/RewriteStatepointsForGC/basics.ll +++ llvm/trunk/test/Transforms/RewriteStatepointsForGC/basics.ll @@ -35,8 +35,8 @@ ; CHECK-LABEL: entry: ; CHECK-NEXT: getelementptr ; CHECK-NEXT: gc.statepoint -; CHECK-NEXT: %derived.relocated = call coldcc i8 addrspace(1)* ; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)* +; CHECK-NEXT: %derived.relocated = call coldcc i8 addrspace(1)* ; CHECK-NEXT: load i8, i8 addrspace(1)* %derived.relocated ; CHECK-NEXT: load i8, i8 addrspace(1)* %obj.relocated ; Tests to make sure we visit both the taken and untaken predeccessor Index: llvm/trunk/test/Transforms/RewriteStatepointsForGC/rematerialize-derived-pointers.ll =================================================================== --- llvm/trunk/test/Transforms/RewriteStatepointsForGC/rematerialize-derived-pointers.ll +++ llvm/trunk/test/Transforms/RewriteStatepointsForGC/rematerialize-derived-pointers.ll @@ -76,10 +76,10 @@ ; CHECK: addrspacecast i32* %ptr1 to i32 addrspace(1)* call void @do_safepoint() [ "deopt"() ] -; CHECK: %base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 7, i32 7) -; CHECK: %base.relocated.casted = bitcast i8 addrspace(1)* %base.relocated to i32 addrspace(1)* -; CHECK: %ptr2.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 7, i32 8) +; CHECK: %ptr2.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 8, i32 7) ; CHECK: %ptr2.relocated.casted = bitcast i8 addrspace(1)* %ptr2.relocated to i32 addrspace(1)* +; CHECK: %base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 8, i32 8) +; CHECK: %base.relocated.casted = bitcast i8 addrspace(1)* %base.relocated to i32 addrspace(1)* call void @use_obj32(i32 addrspace(1)* %base) call void @use_obj32(i32 addrspace(1)* %ptr2) ret void Index: llvm/trunk/test/Transforms/RewriteStatepointsForGC/statepoint-format.ll =================================================================== --- llvm/trunk/test/Transforms/RewriteStatepointsForGC/statepoint-format.ll +++ llvm/trunk/test/Transforms/RewriteStatepointsForGC/statepoint-format.ll @@ -6,7 +6,7 @@ define i64 addrspace(1)* @test_invoke_format(i64 addrspace(1)* %obj, i64 addrspace(1)* %obj1) gc "statepoint-example" personality i32 ()* @personality { ; CHECK-LABEL: @test_invoke_format( ; CHECK-LABEL: entry: -; CHECK: invoke token (i64, i32, i64 addrspace(1)* (i64 addrspace(1)*)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_p1i64p1i64f(i64 2882400000, i32 0, i64 addrspace(1)* (i64 addrspace(1)*)* @callee, i32 1, i32 0, i64 addrspace(1)* %obj, i32 0, i32 0, i64 addrspace(1)* %obj, i64 addrspace(1)* %obj1) +; CHECK: invoke token (i64, i32, i64 addrspace(1)* (i64 addrspace(1)*)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_p1i64p1i64f(i64 2882400000, i32 0, i64 addrspace(1)* (i64 addrspace(1)*)* @callee, i32 1, i32 0, i64 addrspace(1)* %obj, i32 0, i32 0, i64 addrspace(1)* %obj1, i64 addrspace(1)* %obj) entry: %ret_val = invoke i64 addrspace(1)* @callee(i64 addrspace(1)* %obj) to label %normal_return unwind label %exceptional_return