+ // Each set is unique in UsedGlobalSets.
+ std::vector<UsedGlobalSet> UsedGlobalSets;
+
+ // Avoid repeating the create-global-set pattern.
+ auto CreateGlobalSet = [&]() -> UsedGlobalSet & {
+ UsedGlobalSets.emplace_back(Globals.size());
+ return UsedGlobalSets.back();
+ };
+
+ // The first set is the empty set.
+ CreateGlobalSet().UsageCount = 0;
+
+ // We define "close enough" to be "in the same function".
+ // FIXME: Grouping uses by function is way too aggressive, so we should have
+ // a better metric for distance between uses.
+ // The obvious alternative would be to group by BasicBlock, but that's in
+ // turn too conservative..
+ // Anything in between wouldn't be trivial to compute, so just stick with
+ // per-function grouping.
+
+ // The value type is an index into UsedGlobalSets.
+ // The default (0) conveniently points to the empty set.
+ DenseMap<Function *, size_t /*UsedGlobalSetIdx*/> GlobalUsesByFunction;
+
+ // Now, look at each merge-eligible global in turn.
+
+ // Keep track of the sets we already encountered to which we added the
+ // current global.
+ // Each element matches the same-index element in UsedGlobalSets.
+ // This lets us efficiently tell whether a set has already been expanded to
+ // include the current global.
+ std::vector<size_t> EncounteredUGS;
+
+ for (size_t GI = 0, GE = Globals.size(); GI != GE; ++GI) {
+ GlobalVariable *GV = Globals[GI];
+
+ // Reset the encountered sets for this global...
+ std::fill(EncounteredUGS.begin(), EncounteredUGS.end(), 0);
+ // ...and grow it in case we created new sets for the previous global.
+ EncounteredUGS.resize(UsedGlobalSets.size());
+
+ // We might need to create a set that only consists of the current global.
+ // Keep track of its index into UsedGlobalSets.
+ size_t CurGVOnlySetIdx = 0;
+
+ // For each global, look at all its Uses.
+ for (auto &U : GV->uses()) {
+ // This Use might be a ConstantExpr. We're interested in Instruction
+ // users, so look through ConstantExpr...
+ Use *UI, *UE;
+ if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U.getUser())) {
+ if (CE->use_empty())
+ continue;
+ UI = &*CE->use_begin();
+ UE = nullptr;
+ } else if (isa<Instruction>(U.getUser())) {
+ UI = &U;
+ UE = UI->getNext();
+ } else {
+ continue;
+ }
+
+ // ...to iterate on all the instruction users of the global.
+ // Note that we iterate on Uses and not on Users to be able to getNext().
+ for (; UI != UE; UI = UI->getNext()) {
+ Instruction *I = dyn_cast<Instruction>(UI->getUser());
+ if (!I)
+ continue;
+
+ Function *ParentFn = I->getParent()->getParent();
+
+ // If we're only optimizing for size, ignore non-minsize functions.
+ if (OnlyOptimizeForSize && !ParentFn->optForMinSize())
+ continue;
+
+ size_t UGSIdx = GlobalUsesByFunction[ParentFn];
+
+ // If this is the first global the basic block uses, map it to the set
+ // consisting of this global only.
+ if (!UGSIdx) {
+ // If that set doesn't exist yet, create it.
+ if (!CurGVOnlySetIdx) {
+ CurGVOnlySetIdx = UsedGlobalSets.size();
+ CreateGlobalSet().Globals.set(GI);
+ } else {
+ ++UsedGlobalSets[CurGVOnlySetIdx].UsageCount;
+ }
+
+ GlobalUsesByFunction[ParentFn] = CurGVOnlySetIdx;
+ continue;
+ }
+
+ // If we already encountered this BB, just increment the counter.
+ if (UsedGlobalSets[UGSIdx].Globals.test(GI)) {
+ ++UsedGlobalSets[UGSIdx].UsageCount;
+ continue;
+ }
+
+ // If not, the previous set wasn't actually used in this function.
+ --UsedGlobalSets[UGSIdx].UsageCount;
+
+ // If we already expanded the previous set to include this global, just
+ // reuse that expanded set.
+ if (size_t ExpandedIdx = EncounteredUGS[UGSIdx]) {
+ ++UsedGlobalSets[ExpandedIdx].UsageCount;
+ GlobalUsesByFunction[ParentFn] = ExpandedIdx;
+ continue;
+ }
+
+ // If not, create a new set consisting of the union of the previous set
+ // and this global. Mark it as encountered, so we can reuse it later.
+ GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] =
+ UsedGlobalSets.size();
+
+ UsedGlobalSet &NewUGS = CreateGlobalSet();
+ NewUGS.Globals.set(GI);
+ NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals;
+ }
+ }
+ }