Index: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -759,16 +759,19 @@ }; #endif - // Once populated, will contain a mapping from each potentially non-base BDV - // to a lattice value (described above) which corresponds to that BDV. - ConflictStateMapTy states; + // Once populated, will contain the list of base defining values we need to + // analyze and possibly insert parallel base propagation instructions for. + // We use the order of insertion (DFS over the def/use graph) to provide a + // stable deterministic ordering for visiting DenseMaps (which are unordered) + // below. This is important for deterministic compilation. + SmallSetVector VisitOrder; + // Recursively fill in all phis & selects reachable from the initial one // for which we don't already know a definite base value for /* scope */ { - DenseSet Visited; SmallVector Worklist; Worklist.push_back(def); - Visited.insert(def); + VisitOrder.insert(def); while (!Worklist.empty()) { Value *Current = Worklist.pop_back_val(); assert(!isKnownBaseResult(Current) && "why did it get added?"); @@ -781,7 +784,7 @@ return; assert(isExpectedBDVType(Base) && "the only non-base values " "we see should be base defining values"); - if (Visited.insert(Base).second) + if (VisitOrder.insert(Base)) Worklist.push_back(Base); }; if (PHINode *Phi = dyn_cast(Current)) { @@ -799,18 +802,24 @@ llvm_unreachable("unimplemented instruction case"); } } - // The frontier of visited instructions are the ones we might need to - // duplicate, so fill in the starting state for the optimistic algorithm - // that follows. - for (Value *BDV : Visited) { - states[BDV] = BDVState(); - } + } + + // Once populated, will contain a mapping from each potentially non-base BDV + // to a lattice value (described above) which corresponds to that BDV. + ConflictStateMapTy states; + + // The frontier of visited instructions are the ones we might need to + // duplicate, so fill in the starting state for the optimistic algorithm + // that follows. + for (Value *BDV : VisitOrder) { + states[BDV] = BDVState(); } #ifndef NDEBUG DEBUG(dbgs() << "States after initialization:\n"); - for (auto Pair : states) { - DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n"); + for (auto Key : VisitOrder) { + auto State = states[Key]; + DEBUG(dbgs() << " " << State << " for " << *Key << "\n"); } #endif @@ -830,7 +839,10 @@ size_t oldSize = states.size(); #endif progress = false; - // We're only changing keys in this loop, thus safe to keep iterators + // 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 + // much faster. for (auto Pair : states) { Value *v = Pair.first; assert(!isKnownBaseResult(v) && "why did it get added?"); @@ -856,7 +868,6 @@ calculateMeet.meetWith(getStateForInput(EE->getVectorOperand())); } - BDVState oldState = states[v]; BDVState newState = calculateMeet.getResult(); if (oldState != newState) { @@ -871,8 +882,9 @@ #ifndef NDEBUG DEBUG(dbgs() << "States after meet iteration:\n"); - for (auto Pair : states) { - DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n"); + for (auto Key : VisitOrder) { + auto State = states[Key]; + DEBUG(dbgs() << " " << State << " for " << *Key << "\n"); } #endif @@ -880,15 +892,8 @@ // We want to keep naming deterministic in the loop that follows, so // sort the keys before iteration. This is useful in allowing us to // write stable tests. Note that there is no invalidation issue here. - SmallVector Keys; - Keys.reserve(states.size()); - for (auto Pair : states) { - Value *V = Pair.first; - Keys.push_back(V); - } - std::sort(Keys.begin(), Keys.end(), order_by_name); // TODO: adjust naming patterns to avoid this order of iteration dependency - for (Value *V : Keys) { + for (Value *V : VisitOrder) { Instruction *I = cast(V); BDVState State = states[I]; assert(!isKnownBaseResult(I) && "why did it get added?"); @@ -974,10 +979,12 @@ return Base; }; - // Fixup all the inputs of the new PHIs - for (auto Pair : states) { - Instruction *v = cast(Pair.first); - BDVState state = Pair.second; + // Fixup all the inputs of the new PHIs. Visit order needs to be + // deterministic and predictable because we're naming newly created + // instructions. + for (auto *Key : VisitOrder) { + Instruction *v = cast(Key); + BDVState state = states[Key]; assert(!isKnownBaseResult(v) && "why did it get added?"); assert(!state.isUnknown() && "Optimistic algorithm didn't complete!"); @@ -1059,18 +1066,17 @@ // 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 Key : Keys) { - Value *V = Key; - auto State = states[Key]; + for (auto *BDV : VisitOrder) { + auto State = states[BDV]; Value *Base = State.getBase(); - assert(V && Base); - assert(!isKnownBaseResult(V) && "why did it get added?"); + 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] = V; + ReverseMap[Base] = BDV; if (auto *BaseI = dyn_cast(Base)) { NewInsts.insert(BaseI); Worklist.insert(BaseI); @@ -1113,26 +1119,25 @@ // Cache all of our results so we can cheaply reuse them // NOTE: This is actually two caches: one of the base defining value // relation and one of the base pointer relation! FIXME - for (auto item : states) { - Value *v = item.first; - Value *base = item.second.getBase(); - assert(v && base); + for (auto *BDV : VisitOrder) { + Value *base = states[BDV].getBase(); + assert(BDV && base); std::string fromstr = - cache.count(v) ? (cache[v]->hasName() ? cache[v]->getName() : "") + cache.count(BDV) ? (cache[BDV]->hasName() ? cache[BDV]->getName() : "") : "none"; DEBUG(dbgs() << "Updating base value cache" - << " for: " << (v->hasName() ? v->getName() : "") + << " for: " << (BDV->hasName() ? BDV->getName() : "") << " from: " << fromstr << " to: " << (base->hasName() ? base->getName() : "") << "\n"); - if (cache.count(v)) { + if (cache.count(BDV)) { // 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[v]) || cache[v] == base) && + assert((!isKnownBaseResult(cache[BDV]) || cache[BDV] == base) && "base relation should be stable"); } - cache[v] = base; + cache[BDV] = base; } assert(cache.find(def) != cache.end()); return cache[def];