[flang] Refine symbol sorting

[klausler]

Summary

Replace semantics::SymbolSet with alternatives that clarify
whether the set should order its contents by source position
or not. This matters because positionally-ordered sets must
not be used for Symbols that might be subjected to name
replacement during name resolution, and address-ordered
sets must not be used (without sorting) in circumstances
where the order of their contents affects the output of the
compiler.

All set<> and map<> instances in the compiler that are keyed
by Symbols now have explicit Compare types in their template
instantiations. Symbol::operator< is no more.

Resolves lingering portability problems from https://reviews.llvm.org/D98743

[PeteSteinfeld]

All builds, tests, and looks good.

flang/include/flang/Evaluate/constant.h

std::size_t CopyFrom(const Constant &source, std::size_t count,
       ConstantSubscripts &resultSubscripts, const std::vector<int> *dimOrder);
 
 private:
   Scalar<Result> values_; // one contiguous string
   ConstantSubscript length_;
 };
 
 class StructureConstructor;
-using StructureConstructorValues =
-    std::map<SymbolRef, common::CopyableIndirection<Expr<SomeType>>>;
+struct ComponentCompare {
+  bool operator()(SymbolRef x, SymbolRef y) const;
+};
+using StructureConstructorValues = std::map<SymbolRef,
+    common::CopyableIndirection<Expr<SomeType>>, ComponentCompare>;
 
 template <>
 class Constant<SomeDerived>
     : public ConstantBase<SomeDerived, StructureConstructorValues> {
 public:
   using Result = SomeDerived;
   using Element = StructureConstructorValues;
   using Base = ConstantBase<SomeDerived, StructureConstructorValues>;

flang/include/flang/Evaluate/tools.h

 }
 
 // GetLastTarget() returns the rightmost symbol in an object designator's
 // SymbolVector that has the POINTER or TARGET attribute, or a null pointer
 // when none is found.
 const Symbol *GetLastTarget(const SymbolVector &);
 
 // Collects all of the Symbols in an expression
-template <typename A> semantics::SymbolSet CollectSymbols(const A &);
-extern template semantics::SymbolSet CollectSymbols(const Expr<SomeType> &);
-extern template semantics::SymbolSet CollectSymbols(const Expr<SomeInteger> &);
-extern template semantics::SymbolSet CollectSymbols(
+template <typename A> semantics::UnorderedSymbolSet CollectSymbols(const A &);
+extern template semantics::UnorderedSymbolSet CollectSymbols(
+    const Expr<SomeType> &);
+extern template semantics::UnorderedSymbolSet CollectSymbols(
+    const Expr<SomeInteger> &);
+extern template semantics::UnorderedSymbolSet CollectSymbols(
     const Expr<SubscriptInteger> &);
 
 // Predicate: does a variable contain a vector-valued subscript (not a triplet)?
 bool HasVectorSubscript(const Expr<SomeType> &);
 
 // Utilities for attaching the location of the declaration of a symbol
 // of interest to a message, if both pointers are non-null.  Handles
 // the case of USE association gracefully.

flang/include/flang/Semantics/semantics.h

private:
   Scope globalScope_;
   parser::Messages messages_;
   evaluate::FoldingContext foldingContext_;
   ConstructStack constructStack_;
   struct IndexVarInfo {
     parser::CharBlock location;
     IndexVarKind kind;
   };
-  std::map<SymbolRef, const IndexVarInfo> activeIndexVars_;
-  SymbolSet errorSymbols_;
+  std::map<SymbolRef, const IndexVarInfo, SymbolAddressCompare>
+      activeIndexVars_;
+  UnorderedSymbolSet errorSymbols_;
   std::set<std::string> tempNames_;
 };
 
 class Semantics {
 public:
   explicit Semantics(SemanticsContext &context, parser::Program &program,
       parser::CharBlock charBlock, bool debugModuleWriter = false)
       : context_{context}, program_{program} {

flang/include/flang/Semantics/symbol.h

return std::visit(common::visitors{
                           [](const auto &) { return false; },
                       },
         details_);
   }
 
   bool operator==(const Symbol &that) const { return this == &that; }
   bool operator!=(const Symbol &that) const { return !(*this == that); }
 
-  // Symbol comparison is based on the order of cooked source
-  // stream creation and, when both are from the same cooked source,
-  // their positions in that cooked source stream.
-  // (This function is implemented in Evaluate/tools.cpp to
-  // satisfy complicated shared library interdependency.)
-  bool operator<(const Symbol &) const;
-
   int Rank() const {
     return std::visit(
         common::visitors{
             [](const SubprogramDetails &sd) {
               return sd.isFunction() ? sd.result().Rank() : 0;
             },
             [](const GenericDetails &) {
               return 0; /*TODO*/
return std::visit(
           [](const TypeParamDetails &x) { return x.type(); },
           [](const UseDetails &x) { return x.symbol().GetType(); },
           [](const HostAssocDetails &x) { return x.symbol().GetType(); },
           [](const auto &) -> const DeclTypeSpec * { return nullptr; },
       },
       details_);
 }
 
-inline bool operator<(SymbolRef x, SymbolRef y) {
-  return *x < *y; // name source position ordering
+// Sets and maps keyed by Symbols
+
+struct SymbolAddressCompare {
+  bool operator()(const SymbolRef &x, const SymbolRef &y) const {
+    return &*x < &*y;
+  }
+  bool operator()(const MutableSymbolRef &x, const MutableSymbolRef &y) const {
+    return &*x < &*y;
   }
-inline bool operator<(MutableSymbolRef x, MutableSymbolRef y) {
-  return *x < *y; // name source position ordering
+};
+
+// Symbol comparison is based on the order of cooked source
+// stream creation and, when both are from the same cooked source,
+// their positions in that cooked source stream.
+// Don't use this comparator or OrderedSymbolSet to hold
+// Symbols that might be subject to ReplaceName().
+struct SymbolSourcePositionCompare {
+  // These functions are implemented in Evaluate/tools.cpp to
+  // satisfy complicated shared library interdependency.
+  bool operator()(const SymbolRef &, const SymbolRef &) const;
+  bool operator()(const MutableSymbolRef &, const MutableSymbolRef &) const;
+};
+
+using UnorderedSymbolSet = std::set<SymbolRef, SymbolAddressCompare>;
+using OrderedSymbolSet = std::set<SymbolRef, SymbolSourcePositionCompare>;
+
+template <typename A>
+OrderedSymbolSet OrderBySourcePosition(const A &container) {
+  OrderedSymbolSet result;
+  for (SymbolRef x : container) {
+    result.emplace(x);
+  }
+  return result;
 }
-using SymbolSet = std::set<SymbolRef>;
 
 } // namespace Fortran::semantics
 
 // Define required  info so that SymbolRef can be used inside llvm::DenseMap.
 namespace llvm {
 template <> struct DenseMapInfo<Fortran::semantics::SymbolRef> {
   static inline Fortran::semantics::SymbolRef getEmptyKey() {
     auto ptr = DenseMapInfo<const Fortran::semantics::Symbol *>::getEmptyKey();

flang/lib/Evaluate/characteristics.cpp

 DummyProcedure::DummyProcedure(Procedure &&p)
     : procedure{new Procedure{std::move(p)}} {}
 
 bool DummyProcedure::operator==(const DummyProcedure &that) const {
   return attrs == that.attrs && intent == that.intent &&
       procedure.value() == that.procedure.value();
 }
 
-static std::string GetSeenProcs(const semantics::SymbolSet &seenProcs) {
+static std::string GetSeenProcs(
+    const semantics::UnorderedSymbolSet &seenProcs) {
   // Sort the symbols so that they appear in the same order on all platforms
-  std::vector<SymbolRef> sorter{seenProcs.begin(), seenProcs.end()};
-  std::sort(sorter.begin(), sorter.end());
-
+  auto ordered{semantics::OrderBySourcePosition(seenProcs)};
   std::string result;
   llvm::interleave(
-      sorter,
+      ordered,
       [&](const SymbolRef p) { result += '\'' + p->name().ToString() + '\''; },
       [&]() { result += ", "; });
   return result;
 }
 
-// These functions with arguments of type SymbolSet are used with mutually
-// recursive calls when characterizing a Procedure, a DummyArgument, or a
-// DummyProcedure to detect circularly defined procedures as required by
+// These functions with arguments of type UnorderedSymbolSet are used with
+// mutually recursive calls when characterizing a Procedure, a DummyArgument,
+// or a DummyProcedure to detect circularly defined procedures as required by
 // 15.4.3.6, paragraph 2.
 static std::optional<DummyArgument> CharacterizeDummyArgument(
     const semantics::Symbol &symbol, FoldingContext &context,
-    semantics::SymbolSet &seenProcs);
+    semantics::UnorderedSymbolSet &seenProcs);
 
 static std::optional<Procedure> CharacterizeProcedure(
     const semantics::Symbol &original, FoldingContext &context,
-    semantics::SymbolSet &seenProcs) {
+    semantics::UnorderedSymbolSet &seenProcs) {
   Procedure result;
   const auto &symbol{original.GetUltimate()};
   if (seenProcs.find(symbol) != seenProcs.end()) {
     std::string procsList{GetSeenProcs(seenProcs)};
     context.messages().Say(symbol.name(),
         "Procedure '%s' is recursively defined.  Procedures in the cycle:"
         " %s"_err_en_US,
         symbol.name(), procsList);
return std::visit(
           },
           [](const auto &) { return std::optional<Procedure>{}; },
       },
       symbol.details());
 }
 
 static std::optional<DummyProcedure> CharacterizeDummyProcedure(
     const semantics::Symbol &symbol, FoldingContext &context,
-    semantics::SymbolSet &seenProcs) {
+    semantics::UnorderedSymbolSet &seenProcs) {
   if (auto procedure{CharacterizeProcedure(symbol, context, seenProcs)}) {
     // Dummy procedures may not be elemental.  Elemental dummy procedure
     // interfaces are errors when the interface is not intrinsic, and that
     // error is caught elsewhere.  Elemental intrinsic interfaces are
     // made non-elemental.
     procedure->attrs.reset(Procedure::Attr::Elemental);
     DummyProcedure result{std::move(procedure.value())};
     CopyAttrs<DummyProcedure, DummyProcedure::Attr>(symbol, result,

 DummyArgument::~DummyArgument() {}
 
 bool DummyArgument::operator==(const DummyArgument &that) const {
   return u == that.u; // name and passed-object usage are not characteristics
 }
 
 static std::optional<DummyArgument> CharacterizeDummyArgument(
     const semantics::Symbol &symbol, FoldingContext &context,
-    semantics::SymbolSet &seenProcs) {
+    semantics::UnorderedSymbolSet &seenProcs) {
   auto name{symbol.name().ToString()};
   if (symbol.has<semantics::ObjectEntityDetails>()) {
     if (auto obj{DummyDataObject::Characterize(symbol, context)}) {
       return DummyArgument{std::move(name), std::move(obj.value())};
     }
   } else if (auto proc{
                  CharacterizeDummyProcedure(symbol, context, seenProcs)}) {
     return DummyArgument{std::move(name), std::move(proc.value())};
if ((!passIndex || j != *passIndex) &&
       return false;
     }
   }
   return true;
 }
 
 std::optional<Procedure> Procedure::Characterize(
     const semantics::Symbol &original, FoldingContext &context) {
-  semantics::SymbolSet seenProcs;
+  semantics::UnorderedSymbolSet seenProcs;
   return CharacterizeProcedure(original, context, seenProcs);
 }
 
 std::optional<Procedure> Procedure::Characterize(
     const ProcedureDesignator &proc, FoldingContext &context) {
   if (const auto *symbol{proc.GetSymbol()}) {
     if (auto result{characteristics::Procedure::Characterize(
             symbol->GetUltimate(), context)}) {

flang/lib/Evaluate/constant.cpp

 }
 
 std::size_t Constant<SomeDerived>::CopyFrom(const Constant<SomeDerived> &source,
     std::size_t count, ConstantSubscripts &resultSubscripts,
     const std::vector<int> *dimOrder) {
   return Base::CopyFrom(source, count, resultSubscripts, dimOrder);
 }
 
+bool ComponentCompare::operator()(SymbolRef x, SymbolRef y) const {
+  return semantics::SymbolSourcePositionCompare{}(x, y);
+}
+
 INSTANTIATE_CONSTANT_TEMPLATES
 } // namespace Fortran::evaluate

flang/lib/Evaluate/tools.cpp

const Symbol *GetLastTarget(const SymbolVector &symbols) {
   auto iter{std::find_if(std::crbegin(symbols), end, [](const Symbol &x) {
     return x.attrs().HasAny(
         {semantics::Attr::POINTER, semantics::Attr::TARGET});
   })};
   return iter == end ? nullptr : &**iter;
 }
 
 struct CollectSymbolsHelper
-    : public SetTraverse<CollectSymbolsHelper, semantics::SymbolSet> {
-  using Base = SetTraverse<CollectSymbolsHelper, semantics::SymbolSet>;
+    : public SetTraverse<CollectSymbolsHelper, semantics::UnorderedSymbolSet> {
+  using Base = SetTraverse<CollectSymbolsHelper, semantics::UnorderedSymbolSet>;
   CollectSymbolsHelper() : Base{*this} {}
   using Base::operator();
-  semantics::SymbolSet operator()(const Symbol &symbol) const {
+  semantics::UnorderedSymbolSet operator()(const Symbol &symbol) const {
     return {symbol};
   }
 };
-template <typename A> semantics::SymbolSet CollectSymbols(const A &x) {
+template <typename A> semantics::UnorderedSymbolSet CollectSymbols(const A &x) {
   return CollectSymbolsHelper{}(x);
 }
-template semantics::SymbolSet CollectSymbols(const Expr<SomeType> &);
-template semantics::SymbolSet CollectSymbols(const Expr<SomeInteger> &);
-template semantics::SymbolSet CollectSymbols(const Expr<SubscriptInteger> &);
+template semantics::UnorderedSymbolSet CollectSymbols(const Expr<SomeType> &);
+template semantics::UnorderedSymbolSet CollectSymbols(
+    const Expr<SomeInteger> &);
+template semantics::UnorderedSymbolSet CollectSymbols(
+    const Expr<SubscriptInteger> &);
 
 // HasVectorSubscript()
 struct HasVectorSubscriptHelper : public AnyTraverse<HasVectorSubscriptHelper> {
   using Base = AnyTraverse<HasVectorSubscriptHelper>;
   HasVectorSubscriptHelper() : Base{*this} {}
   using Base::operator();
   bool operator()(const Subscript &ss) const {
     return !std::holds_alternative<Triplet>(ss.u) && ss.Rank() > 0;
return std::count_if(
       });
 }
 
 const Symbol &GetUsedModule(const UseDetails &details) {
   return DEREF(details.symbol().owner().symbol());
 }
 
 static const Symbol *FindFunctionResult(
-    const Symbol &original, SymbolSet &seen) {
+    const Symbol &original, UnorderedSymbolSet &seen) {
   const Symbol &root{GetAssociationRoot(original)};
   ;
   if (!seen.insert(root).second) {
     return nullptr; // don't loop
   }
   return std::visit(
       common::visitors{[](const SubprogramDetails &subp) {
                          return subp.isFunction() ? &subp.result() : nullptr;
                        },
           [&](const ProcEntityDetails &proc) {
             const Symbol *iface{proc.interface().symbol()};
             return iface ? FindFunctionResult(*iface, seen) : nullptr;
           },
           [&](const ProcBindingDetails &binding) {
             return FindFunctionResult(binding.symbol(), seen);
           },
           [](const auto &) -> const Symbol * { return nullptr; }},
       root.details());
 }
 
 const Symbol *FindFunctionResult(const Symbol &symbol) {
-  SymbolSet seen;
+  UnorderedSymbolSet seen;
   return FindFunctionResult(symbol, seen);
 }
 
 // These are here in Evaluate/tools.cpp so that Evaluate can use
 // them; they cannot be defined in symbol.h due to the dependence
 // on Scope.
 
-bool Symbol::operator<(const Symbol &that) const {
-  return GetSemanticsContext().allCookedSources().Precedes(name_, that.name_);
+bool SymbolSourcePositionCompare::operator()(
+    const SymbolRef &x, const SymbolRef &y) const {
+  return x->GetSemanticsContext().allCookedSources().Precedes(
+      x->name(), y->name());
+}
+bool SymbolSourcePositionCompare::operator()(
+    const MutableSymbolRef &x, const MutableSymbolRef &y) const {
+  return x->GetSemanticsContext().allCookedSources().Precedes(
+      x->name(), y->name());
 }
 
 SemanticsContext &Symbol::GetSemanticsContext() const {
   return DEREF(owner_).context();
 }
 
 } // namespace Fortran::semantics

flang/lib/Parser/provenance.cpp

void AllCookedSources::Dump(llvm::raw_ostream &o) const {
   o << "AllSources:\n";
   allSources_.Dump(o);
   for (const auto &c : cooked_) {
     c.Dump(o);
   }
 }
 
 bool AllCookedSources::Precedes(CharBlock x, CharBlock y) const {
-  const CookedSource *ySource{Find(y)};
   if (const CookedSource * xSource{Find(x)}) {
-    if (ySource) {
-      int xNum{xSource->number()};
-      int yNum{ySource->number()};
-      return xNum < yNum || (xNum == yNum && x.begin() < y.begin());
+    if (xSource->AsCharBlock().Contains(y)) {
+      return x.begin() < y.begin();
+    } else if (const CookedSource * ySource{Find(y)}) {
+      return xSource->number() < ySource->number();
     } else {
       return true; // by fiat, all cooked source < anything outside
     }
-  } else if (ySource) {
+  } else if (Find(y)) {
     return false;
   } else {
     // Both names are compiler-created (SaveTempName).
     return x < y;
   }
 }
 
 void AllCookedSources::Register(CookedSource &cooked) {
   index_.emplace(cooked.AsCharBlock(), cooked);
   cooked.set_number(static_cast<int>(index_.size()));
 }
 
 } // namespace Fortran::parser

flang/lib/Semantics/check-declarations.cpp

private:
   evaluate::FoldingContext &foldingContext_{context_.foldingContext()};
   parser::ContextualMessages &messages_{foldingContext_.messages()};
   const Scope *scope_{nullptr};
   bool scopeIsUninstantiatedPDT_{false};
   // This symbol is the one attached to the innermost enclosing scope
   // that has a symbol.
   const Symbol *innermostSymbol_{nullptr};
   // Cache of calls to Procedure::Characterize(Symbol)
-  std::map<SymbolRef, std::optional<Procedure>> characterizeCache_;
+  std::map<SymbolRef, std::optional<Procedure>, SymbolAddressCompare>
+      characterizeCache_;
 };
 
 class DistinguishabilityHelper {
 public:
   DistinguishabilityHelper(SemanticsContext &context) : context_{context} {}
   void Add(const Symbol &, GenericKind, const Symbol &, const Procedure &);
   void Check(const Scope &);
 

flang/lib/Semantics/check-do-forall.cpp

void CheckDoConcurrent(const parser::DoConstruct &doConstruct) {
     CheckConcurrentLoopControl(*loopControl);
     CheckLocalitySpecs(*loopControl, block);
   }
 
   // Return a set of symbols whose names are in a Local locality-spec.  Look
   // the names up in the scope that encloses the DO construct to avoid getting
   // the local versions of them.  Then follow the host-, use-, and
   // construct-associations to get the root symbols
-  SymbolSet GatherLocals(
+  UnorderedSymbolSet GatherLocals(
       const std::list<parser::LocalitySpec> &localitySpecs) const {
-    SymbolSet symbols;
+    UnorderedSymbolSet symbols;
     const Scope &parentScope{
         context_.FindScope(currentStatementSourcePosition_).parent()};
     // Loop through the LocalitySpec::Local locality-specs
     for (const auto &ls : localitySpecs) {
       if (const auto *names{std::get_if<parser::LocalitySpec::Local>(&ls.u)}) {
         // Loop through the names in the Local locality-spec getting their
         // symbols
         for (const parser::Name &name : names->v) {
           if (const Symbol * symbol{parentScope.FindSymbol(name.source)}) {
             symbols.insert(ResolveAssociations(*symbol));
           }
         }
       }
     }
     return symbols;
   }
 
-  static SymbolSet GatherSymbolsFromExpression(const parser::Expr &expression) {
-    SymbolSet result;
+  static UnorderedSymbolSet GatherSymbolsFromExpression(
+      const parser::Expr &expression) {
+    UnorderedSymbolSet result;
     if (const auto *expr{GetExpr(expression)}) {
       for (const Symbol &symbol : evaluate::CollectSymbols(*expr)) {
         result.insert(ResolveAssociations(symbol));
       }
     }
     return result;
   }
 
   // C1121 - procedures in mask must be pure
   void CheckMaskIsPure(const parser::ScalarLogicalExpr &mask) const {
-    SymbolSet references{GatherSymbolsFromExpression(mask.thing.thing.value())};
-    for (const Symbol &ref : references) {
+    UnorderedSymbolSet references{
+        GatherSymbolsFromExpression(mask.thing.thing.value())};
+    for (const Symbol &ref : OrderBySourcePosition(references)) {
       if (IsProcedure(ref) && !IsPureProcedure(ref)) {
         context_.SayWithDecl(ref, parser::Unwrap<parser::Expr>(mask)->source,
             "%s mask expression may not reference impure procedure '%s'"_err_en_US,
             LoopKindName(), ref.name());
         return;
       }
     }
   }
 
-  void CheckNoCollisions(const SymbolSet &refs, const SymbolSet &uses,
-      parser::MessageFixedText &&errorMessage,
+  void CheckNoCollisions(const UnorderedSymbolSet &refs,
+      const UnorderedSymbolSet &uses, parser::MessageFixedText &&errorMessage,
       const parser::CharBlock &refPosition) const {
-    for (const Symbol &ref : refs) {
+    for (const Symbol &ref : OrderBySourcePosition(refs)) {
       if (uses.find(ref) != uses.end()) {
         context_.SayWithDecl(ref, refPosition, std::move(errorMessage),
             LoopKindName(), ref.name());
         return;
       }
     }
   }
 
-  void HasNoReferences(
-      const SymbolSet &indexNames, const parser::ScalarIntExpr &expr) const {
+  void HasNoReferences(const UnorderedSymbolSet &indexNames,
+      const parser::ScalarIntExpr &expr) const {
     CheckNoCollisions(GatherSymbolsFromExpression(expr.thing.thing.value()),
         indexNames,
         "%s limit expression may not reference index variable '%s'"_err_en_US,
         expr.thing.thing.value().source);
   }
 
   // C1129, names in local locality-specs can't be in mask expressions
-  void CheckMaskDoesNotReferenceLocal(
-      const parser::ScalarLogicalExpr &mask, const SymbolSet &localVars) const {
+  void CheckMaskDoesNotReferenceLocal(const parser::ScalarLogicalExpr &mask,
+      const UnorderedSymbolSet &localVars) const {
     CheckNoCollisions(GatherSymbolsFromExpression(mask.thing.thing.value()),
         localVars,
         "%s mask expression references variable '%s'"
         " in LOCAL locality-spec"_err_en_US,
         mask.thing.thing.value().source);
   }
 
   // C1129, names in local locality-specs can't be in limit or step
   // expressions
-  void CheckExprDoesNotReferenceLocal(
-      const parser::ScalarIntExpr &expr, const SymbolSet &localVars) const {
+  void CheckExprDoesNotReferenceLocal(const parser::ScalarIntExpr &expr,
+      const UnorderedSymbolSet &localVars) const {
     CheckNoCollisions(GatherSymbolsFromExpression(expr.thing.thing.value()),
         localVars,
         "%s expression references variable '%s'"
         " in LOCAL locality-spec"_err_en_US,
         expr.thing.thing.value().source);
   }
 
   // C1130, DEFAULT(NONE) locality requires names to be in locality-specs to
private:
 
   // C1123, concurrent limit or step expressions can't reference index-names
   void CheckConcurrentHeader(const parser::ConcurrentHeader &header) const {
     if (const auto &mask{
             std::get<std::optional<parser::ScalarLogicalExpr>>(header.t)}) {
       CheckMaskIsPure(*mask);
     }
     auto &controls{std::get<std::list<parser::ConcurrentControl>>(header.t)};
-    SymbolSet indexNames;
+    UnorderedSymbolSet indexNames;
     for (const parser::ConcurrentControl &control : controls) {
       const auto &indexName{std::get<parser::Name>(control.t)};
       if (indexName.symbol) {
         indexNames.insert(*indexName.symbol);
       }
     }
     if (!indexNames.empty()) {
       for (const parser::ConcurrentControl &control : controls) {
private:
   void CheckLocalitySpecs(
       const parser::LoopControl &control, const parser::Block &block) const {
     const auto &concurrent{
         std::get<parser::LoopControl::Concurrent>(control.u)};
     const auto &header{std::get<parser::ConcurrentHeader>(concurrent.t)};
     const auto &localitySpecs{
         std::get<std::list<parser::LocalitySpec>>(concurrent.t)};
     if (!localitySpecs.empty()) {
-      const SymbolSet &localVars{GatherLocals(localitySpecs)};
+      const UnorderedSymbolSet &localVars{GatherLocals(localitySpecs)};
       for (const auto &c : GetControls(control)) {
         CheckExprDoesNotReferenceLocal(std::get<1>(c.t), localVars);
         CheckExprDoesNotReferenceLocal(std::get<2>(c.t), localVars);
         if (const auto &expr{
                 std::get<std::optional<parser::ScalarIntExpr>>(c.t)}) {
           CheckExprDoesNotReferenceLocal(*expr, localVars);
         }
       }
if (auto bad{FindImpureCall(context_.foldingContext(), x)}) {
           LoopKindName());
     }
   }
 
   // Each index should be used on the LHS of each assignment in a FORALL
   void CheckForallIndexesUsed(const evaluate::Assignment &assignment) {
     SymbolVector indexVars{context_.GetIndexVars(IndexVarKind::FORALL)};
     if (!indexVars.empty()) {
-      SymbolSet symbols{evaluate::CollectSymbols(assignment.lhs)};
+      UnorderedSymbolSet symbols{evaluate::CollectSymbols(assignment.lhs)};
       std::visit(
           common::visitors{
               [&](const evaluate::Assignment::BoundsSpec &spec) {
                 for (const auto &bound : spec) {
 // TODO: this is working around missing std::set::merge in some versions of
 // clang that we are building with
 #ifdef __clang__
                   auto boundSymbols{evaluate::CollectSymbols(bound)};

flang/lib/Semantics/check-omp-structure.cpp

if (auto *clause{FindClause(llvm::omp::Clause::OMPC_simdlen)}) {
                   "The parameter of the SIMDLEN clause must be less than or "
                   "equal to the parameter of the SAFELEN clause"_err_en_US);
             }
           }
         }
       }
     }
     // A list-item cannot appear in more than one aligned clause
-    semantics::SymbolSet alignedVars;
+    semantics::UnorderedSymbolSet alignedVars;
     auto clauseAll = FindClauses(llvm::omp::Clause::OMPC_aligned);
     for (auto itr = clauseAll.first; itr != clauseAll.second; ++itr) {
       const auto &alignedClause{
           std::get<parser::OmpClause::Aligned>(itr->second->u)};
       const auto &alignedNameList{
           std::get<std::list<parser::Name>>(alignedClause.v.t)};
       for (auto const &var : alignedNameList) {
         if (alignedVars.count(*(var.symbol)) == 1) {

flang/lib/Semantics/compute-offsets.cpp

private:
   void DoSymbol(Symbol &);
   SizeAndAlignment GetSizeAndAlignment(const Symbol &, bool entire);
   std::size_t Align(std::size_t, std::size_t);
 
   SemanticsContext &context_;
   std::size_t offset_{0};
   std::size_t alignment_{1};
   // symbol -> symbol+offset that determines its location, from EQUIVALENCE
-  std::map<MutableSymbolRef, SymbolAndOffset> dependents_;
+  std::map<MutableSymbolRef, SymbolAndOffset, SymbolAddressCompare> dependents_;
   // base symbol -> SizeAndAlignment for each distinct EQUIVALENCE block
-  std::map<MutableSymbolRef, SizeAndAlignment> equivalenceBlock_;
+  std::map<MutableSymbolRef, SizeAndAlignment, SymbolAddressCompare>
+      equivalenceBlock_;
 };
 
 void ComputeOffsetsHelper::Compute(Scope &scope) {
   for (Scope &child : scope.children()) {
     ComputeOffsets(context_, child);
   }
   if (scope.symbol() && scope.IsParameterizedDerivedType()) {
     return; // only process instantiations of parameterized derived types

flang/lib/Semantics/mod-file.cpp

public:
   const std::set<SourceName> &imports() const { return imports_; }
   void Collect();
 
 private:
   const Symbol &symbol_;
   const Scope &scope_;
   bool isInterface_{false};
   SymbolVector need_; // symbols that are needed
-  SymbolSet needSet_; // symbols already in need_
-  SymbolSet useSet_; // use-associations that might be needed
+  UnorderedSymbolSet needSet_; // symbols already in need_
+  UnorderedSymbolSet useSet_; // use-associations that might be needed
   std::set<SourceName> imports_; // imports from host that are needed
 
   void DoSymbol(const Symbol &);
   void DoSymbol(const SourceName &, const Symbol &);
   void DoType(const DeclTypeSpec *);
   void DoBound(const Bound &);
   void DoParamValue(const ParamValue &);
   bool NeedImport(const SourceName &, const Symbol &);
void CollectSymbols(
   // location of a symbol's name is the first "real" use.
   std::sort(sorted.begin(), sorted.end(), [](SymbolRef x, SymbolRef y) {
     return NameInModuleFile(x).begin() < NameInModuleFile(y).begin();
   });
   sorted.insert(sorted.end(), namelist.begin(), namelist.end());
   for (const auto &pair : scope.commonBlocks()) {
     sorted.push_back(*pair.second);
   }
-  std::sort(sorted.end() - commonSize, sorted.end());
+  std::sort(
+      sorted.end() - commonSize, sorted.end(), SymbolSourcePositionCompare{});
 }
 
 void PutEntity(llvm::raw_ostream &os, const Symbol &symbol) {
   std::visit(
       common::visitors{
           [&](const ObjectEntityDetails &) { PutObjectEntity(os, symbol); },
           [&](const ProcEntityDetails &) { PutProcEntity(os, symbol); },
           [&](const TypeParamDetails &) { PutTypeParam(os, symbol); },

flang/lib/Semantics/resolve-directives.cpp

protected:
   const parser::Name &GetLoopIndex(const parser::DoConstruct &);
   const parser::DoConstruct *GetDoConstructIf(
       const parser::ExecutionPartConstruct &);
   Symbol *DeclarePrivateAccessEntity(
       const parser::Name &, Symbol::Flag, Scope &);
   Symbol *DeclarePrivateAccessEntity(Symbol &, Symbol::Flag, Scope &);
   Symbol *DeclareOrMarkOtherAccessEntity(const parser::Name &, Symbol::Flag);
 
-  SymbolSet dataSharingAttributeObjects_; // on one directive
+  UnorderedSymbolSet dataSharingAttributeObjects_; // on one directive
   SemanticsContext &context_;
   std::vector<DirContext> dirContext_; // used as a stack
 };
 
 class AccAttributeVisitor : DirectiveAttributeVisitor<llvm::acc::Directive> {
 public:
   explicit AccAttributeVisitor(SemanticsContext &context)
       : DirectiveAttributeVisitor(context) {}
private:
 
   static constexpr Symbol::Flags ompFlagsRequireMark{
       Symbol::Flag::OmpThreadprivate};
 
   static constexpr Symbol::Flags dataCopyingAttributeFlags{
       Symbol::Flag::OmpCopyIn, Symbol::Flag::OmpCopyPrivate};
 
   std::vector<const parser::Name *> allocateNames_; // on one directive
-  SymbolSet privateDataSharingAttributeObjects_; // on one directive
-  SymbolSet stmtFunctionExprSymbols_;
+  UnorderedSymbolSet privateDataSharingAttributeObjects_; // on one directive
+  UnorderedSymbolSet stmtFunctionExprSymbols_;
   std::multimap<const parser::Label,
       std::pair<parser::CharBlock, std::optional<DirContext>>>
       sourceLabels_;
   std::map<const parser::Label,
       std::pair<parser::CharBlock, std::optional<DirContext>>>
       targetLabels_;
   parser::CharBlock currentStatementSource_;
 

flang/lib/Semantics/resolve-names.cpp

specificProcs_.emplace(
         GetGenericInfo().symbol, std::make_pair(&name, kind));
   }
 }
 
 // By now we should have seen all specific procedures referenced by name in
 // this generic interface. Resolve those names to symbols.
 void InterfaceVisitor::ResolveSpecificsInGeneric(Symbol &generic) {
   auto &details{generic.get<GenericDetails>()};
-  SymbolSet symbolsSeen;
+  UnorderedSymbolSet symbolsSeen;
   for (const Symbol &symbol : details.specificProcs()) {
     symbolsSeen.insert(symbol);
   }
   auto range{specificProcs_.equal_range(&generic)};
   for (auto it{range.first}; it != range.second; ++it) {
     auto *name{it->second.first};
     auto kind{it->second.second};
     const auto *symbol{FindSymbol(*name)};
if (symbol.attrs().test(Attr::EXTERNAL)) {
       ConvertToProcEntity(symbol);
     }
     return symbol;
   }
 }
 
 bool DeclarationVisitor::HasCycle(
     const Symbol &procSymbol, const ProcInterface &interface) {
-  SymbolSet procsInCycle;
+  OrderedSymbolSet procsInCycle;
   procsInCycle.insert(procSymbol);
   const ProcInterface *thisInterface{&interface};
   bool haveInterface{true};
   while (haveInterface) {
     haveInterface = false;
     if (const Symbol * interfaceSymbol{thisInterface->symbol()}) {
       if (procsInCycle.count(*interfaceSymbol) > 0) {
         for (const auto &procInCycle : procsInCycle) {

flang/lib/Semantics/scope.cpp

 template <typename T>
 static std::vector<common::Reference<T>> GetSortedSymbols(
     std::map<SourceName, MutableSymbolRef> symbols) {
   std::vector<common::Reference<T>> result;
   result.reserve(symbols.size());
   for (auto &pair : symbols) {
     result.push_back(*pair.second);
   }
-  std::sort(result.begin(), result.end());
+  std::sort(result.begin(), result.end(), SymbolSourcePositionCompare{});
   return result;
 }
 
 MutableSymbolVector Scope::GetSymbols() {
   return GetSortedSymbols<Symbol>(symbols_);
 }
 SymbolVector Scope::GetSymbols() const {
   return GetSortedSymbols<const Symbol>(symbols_);

flang/test/Semantics/resolve102.f90

Subroutine sub(p2)
       Procedure(sub1) :: p2
     End Subroutine
 End Program
 
 program twoCycle
   !ERROR: The interface for procedure 'p1' is recursively defined
   !ERROR: The interface for procedure 'p2' is recursively defined
   procedure(p1) p2
-  !ERROR: 'p2' must be an abstract interface or a procedure with an explicit interface
   procedure(p2) p1
   call p1
   call p2
 end program
 
 program threeCycle
   !ERROR: The interface for procedure 'p1' is recursively defined
-  !ERROR: 'p1' must be an abstract interface or a procedure with an explicit interface
   !ERROR: The interface for procedure 'p2' is recursively defined
   procedure(p1) p2
-  !ERROR: 'p2' must be an abstract interface or a procedure with an explicit interface
   !ERROR: The interface for procedure 'p3' is recursively defined
   procedure(p2) p3
   procedure(p3) p1
   call p1
   call p2
   call p3
 end program