[ADT/STLExtras.h] - Add llvm::is_sorted wrapper and update callers.

[grimar]

Summary

It can be used to avoid passing the begin and the end of a range.
This makes the code shorter and it is consistent with another
wrappers we already have.

[MaskRay]

Looks great! Hope another reviewer can confirm.

llvm/lib/IR/AsmWriter.cpp

231–233

This can be further simplified to llvm::is_sorted(lll, llvm::less_second())

llvm/lib/IR/Attributes.cpp

1022–1027

llvm::is_sorted(..., llvm::less_first())

[dblaikie]

Sounds good to me

[grimar]

llvm/lib/IR/AsmWriter.cpp

231–233

I was not aware of llvm::less_*(), thanks!

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

#define ANALYZER_OPTION(TYPE, NAME, CMDFLAG, DESC, DEFAULT_VAL)                \
   llvm::StringLiteral(CMDFLAG),
 
 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.def"
 #undef ANALYZER_OPTION
 #undef ANALYZER_OPTION_DEPENDS_ON_USER_MODE
   };
 
   bool isUnknownAnalyzerConfig(StringRef Name) const {
-
-    assert(std::is_sorted(AnalyzerConfigCmdFlags.begin(),
-                          AnalyzerConfigCmdFlags.end()));
+    assert(llvm::is_sorted(AnalyzerConfigCmdFlags));
 
     return !std::binary_search(AnalyzerConfigCmdFlags.begin(),
                                AnalyzerConfigCmdFlags.end(), Name);
   }
 
   AnalyzerOptions()
       : DisableAllCheckers(false), ShowCheckerHelp(false),
         ShowCheckerHelpAlpha(false), ShowCheckerHelpDeveloper(false),

clang/lib/CodeGen/CGBuiltin.cpp

 static bool AArch64SVEIntrinsicsProvenSorted = false;
 
 static const ARMVectorIntrinsicInfo *
 findARMVectorIntrinsicInMap(ArrayRef<ARMVectorIntrinsicInfo> IntrinsicMap,
                             unsigned BuiltinID, bool &MapProvenSorted) {
 
 #ifndef NDEBUG
   if (!MapProvenSorted) {
-    assert(std::is_sorted(std::begin(IntrinsicMap), std::end(IntrinsicMap)));
+    assert(llvm::is_sorted(IntrinsicMap));
     MapProvenSorted = true;
   }
 #endif
 
   const ARMVectorIntrinsicInfo *Builtin =
       llvm::lower_bound(IntrinsicMap, BuiltinID);
 
   if (Builtin != IntrinsicMap.end() && Builtin->BuiltinID == BuiltinID)

clang/lib/CodeGen/CGObjCMac.cpp

llvm::Constant *IvarLayoutBuilder::buildBitmap(CGObjCCommonMac &CGObjC,
   assert(!IvarsInfo.empty() && "generating bitmap for no data");
 
   // Sort the ivar info on byte position in case we encounterred a
   // union nested in the ivar list.
   if (IsDisordered) {
     // This isn't a stable sort, but our algorithm should handle it fine.
     llvm::array_pod_sort(IvarsInfo.begin(), IvarsInfo.end());
   } else {
-    assert(std::is_sorted(IvarsInfo.begin(), IvarsInfo.end()));
+    assert(llvm::is_sorted(IvarsInfo));
   }
   assert(IvarsInfo.back().Offset < InstanceEnd);
 
   assert(buffer.empty());
 
   // Skip the next N words.
   auto skip = [&](unsigned numWords) {
     assert(numWords > 0);

clang/lib/Format/Format.cpp

static void sortCppIncludes(const FormatStyle &Style,
   int CurrentCategory = Includes.front().Category;
 
   // If the #includes are out of order, we generate a single replacement fixing
   // the entire block. Otherwise, no replacement is generated.
   // In case Style.IncldueStyle.IncludeBlocks != IBS_Preserve, this check is not
   // enough as additional newlines might be added or removed across #include
   // blocks. This we handle below by generating the updated #imclude blocks and
   // comparing it to the original.
-  if (Indices.size() == Includes.size() &&
-      std::is_sorted(Indices.begin(), Indices.end()) &&
+  if (Indices.size() == Includes.size() && llvm::is_sorted(Indices) &&
       Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Preserve)
     return;
 
   std::string result;
   for (unsigned Index : Indices) {
     if (!result.empty()) {
       result += "\n";
       if (Style.IncludeStyle.IncludeBlocks ==

clang/lib/Format/SortJavaScriptImports.cpp

if (References.empty())
       return {Result, 0};
 
     SmallVector<unsigned, 16> Indices;
     for (unsigned i = 0, e = References.size(); i != e; ++i)
       Indices.push_back(i);
     llvm::stable_sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
       return References[LHSI] < References[RHSI];
     });
-    bool ReferencesInOrder = std::is_sorted(Indices.begin(), Indices.end());
+    bool ReferencesInOrder = llvm::is_sorted(Indices);
 
     std::string ReferencesText;
     bool SymbolsInOrder = true;
     for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
       JsModuleReference Reference = References[Indices[i]];
       if (appendReference(ReferencesText, Reference))
         SymbolsInOrder = false;
       if (i + 1 < e) {

clang/lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp

 static std::conditional_t<std::is_const<CheckerOrPackageInfoList>::value,
                           typename CheckerOrPackageInfoList::const_iterator,
                           typename CheckerOrPackageInfoList::iterator>
 binaryFind(CheckerOrPackageInfoList &Collection, StringRef FullName) {
 
   using CheckerOrPackage = typename CheckerOrPackageInfoList::value_type;
   using CheckerOrPackageFullNameLT = FullNameLT<CheckerOrPackage>;
 
-  assert(std::is_sorted(Collection.begin(), Collection.end(),
-                        CheckerOrPackageFullNameLT{}) &&
+  assert(llvm::is_sorted(Collection, CheckerOrPackageFullNameLT{}) &&
          "In order to efficiently gather checkers/packages, this function "
          "expects them to be already sorted!");
 
   return llvm::lower_bound(Collection, CheckerOrPackage(FullName),
                            CheckerOrPackageFullNameLT{});
 }
 
 static constexpr char PackageSeparator = '.';

clang/lib/Tooling/Syntax/Tokens.cpp

TokenBuffer build() && {
     // If any tokens remain in any of the files, they didn't expand to anything.
     // Create empty mappings up until the end of the file.
     for (const auto &File : Result.Files)
       discard(File.first);
 
 #ifndef NDEBUG
     for (auto &pair : Result.Files) {
       auto &mappings = pair.second.Mappings;
-      assert(std::is_sorted(
-          mappings.begin(), mappings.end(),
-          [](const TokenBuffer::Mapping &M1, const TokenBuffer::Mapping &M2) {
-            return M1.BeginSpelled < M2.BeginSpelled &&
-                   M1.EndSpelled < M2.EndSpelled &&
-                   M1.BeginExpanded < M2.BeginExpanded &&
-                   M1.EndExpanded < M2.EndExpanded;
-          }));
+      assert(llvm::is_sorted(mappings, [](const TokenBuffer::Mapping &M1,
+                                          const TokenBuffer::Mapping &M2) {
     }
 #endif
 
     return std::move(Result);
   }
 
 private:
   // Consume a sequence of spelled tokens that didn't expand to anything.

lld/wasm/InputFiles.cpp

 
 template <class T>
 static void setRelocs(const std::vector<T *> &chunks,
                       const WasmSection *section) {
   if (!section)
     return;
 
   ArrayRef<WasmRelocation> relocs = section->Relocations;
-  assert(std::is_sorted(relocs.begin(), relocs.end(),
-                        [](const WasmRelocation &r1, const WasmRelocation &r2) {
-                          return r1.Offset < r2.Offset;
-                        }));
-  assert(std::is_sorted(
-      chunks.begin(), chunks.end(), [](InputChunk *c1, InputChunk *c2) {
-        return c1->getInputSectionOffset() < c2->getInputSectionOffset();
-      }));
+  assert(llvm::is_sorted(
+      relocs, [](const WasmRelocation &r1, const WasmRelocation &r2) {
+  assert(llvm::is_sorted(chunks, [](InputChunk *c1, InputChunk *c2) {
 
   auto relocsNext = relocs.begin();
   auto relocsEnd = relocs.end();
   auto relocLess = [](const WasmRelocation &r, uint32_t val) {
     return r.Offset < val;
   };
   for (InputChunk *c : chunks) {
     auto relocsStart = std::lower_bound(relocsNext, relocsEnd,

llvm/include/llvm/ADT/CoalescingBitVector.h

private:
 
   /// Record the overlaps between \p this and \p Other in \p Overlaps. Return
   /// true if there is any overlap.
   bool getOverlaps(const ThisT &Other,
                    SmallVectorImpl<IntervalT> &Overlaps) const {
     for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals);
          I.valid(); ++I)
       Overlaps.emplace_back(I.start(), I.stop());
-    assert(std::is_sorted(Overlaps.begin(), Overlaps.end(),
+    assert(llvm::is_sorted(Overlaps,
                            [](IntervalT LHS, IntervalT RHS) {
                              return LHS.second < RHS.first;
                            }) &&
            "Overlaps must be sorted");
     return !Overlaps.empty();
   }
 
   /// Given the set of overlaps between this and some other bitvector, and an
   /// interval [Start, Stop] from that bitvector, determine the portions of the
   /// interval which do not overlap with this.
   void getNonOverlappingParts(IndexT Start, IndexT Stop,

llvm/include/llvm/ADT/STLExtras.h

 
 /// Wrapper function around std::find to detect if an element exists
 /// in a container.
 template <typename R, typename E>
 bool is_contained(R &&Range, const E &Element) {
   return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
 }
 
+/// Wrapper function around std::is_sorted to check if elements in a range \p R
+/// are sorted with respect to a comparator \p C.
+template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) {
+  return std::is_sorted(adl_begin(Range), adl_end(Range), C);
+}
+
+/// Wrapper function around std::is_sorted to check if elements in a range \p R
+/// are sorted in non-descending order.
+template <typename R> bool is_sorted(R &&Range) {
+  return std::is_sorted(adl_begin(Range), adl_end(Range));
+}
+
 /// Wrapper function around std::count to count the number of times an element
 /// \p Element occurs in the given range \p Range.
 template <typename R, typename E> auto count(R &&Range, const E &Element) {
   return std::count(adl_begin(Range), adl_end(Range), Element);
 }
 
 /// Wrapper function around std::count_if to count the number of times an
 /// element satisfying a given predicate occurs in a range.

llvm/include/llvm/CodeGen/LiveInterval.h

public:
     /// Stores indexes from the input index sequence R at which this LiveRange
     /// is live to the output O iterator.
     /// R is a range of _ascending sorted_ _random_ access iterators
     /// to the input indexes. Indexes stored at O are ascending sorted so it
     /// can be used directly in the subsequent search (for example for
     /// subranges). Returns true if found at least one index.
     template <typename Range, typename OutputIt>
     bool findIndexesLiveAt(Range &&R, OutputIt O) const {
-      assert(std::is_sorted(R.begin(), R.end()));
+      assert(llvm::is_sorted(R));
       auto Idx = R.begin(), EndIdx = R.end();
       auto Seg = segments.begin(), EndSeg = segments.end();
       bool Found = false;
       while (Idx != EndIdx && Seg != EndSeg) {
         // if the Seg is lower find first segment that is above Idx using binary
         // search
         if (Seg->end <= *Idx) {
           Seg = std::upper_bound(

llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp

bool CFLAndersAAResult::FunctionInfo::mayAlias(
   auto Itr = AliasMap.find(LHS);
   if (Itr != AliasMap.end()) {
 
     // Find out all (X, Offset) where X == RHS
     auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
       return std::less<const Value *>()(LHS.Val, RHS.Val);
     };
 #ifdef EXPENSIVE_CHECKS
-    assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), Comparator));
+    assert(llvm::is_sorted(Itr->second, Comparator));
 #endif
     auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
                                       OffsetValue{RHS, 0}, Comparator);
 
     if (RangePair.first != RangePair.second) {
       // Be conservative about unknown sizes
       if (MaybeLHSSize == LocationSize::unknown() ||
           MaybeRHSSize == LocationSize::unknown())

llvm/lib/Analysis/LoopCacheAnalysis.cpp

static Loop *getInnerMostLoop(const LoopVectorTy &Loops) {
   Loop *LastLoop = Loops.back();
   Loop *ParentLoop = LastLoop->getParentLoop();
 
   if (ParentLoop == nullptr) {
     assert(Loops.size() == 1 && "Expecting a single loop");
     return LastLoop;
   }
 
-  return (std::is_sorted(Loops.begin(), Loops.end(),
+  return (llvm::is_sorted(Loops,
                           [](const Loop *L1, const Loop *L2) {
                             return L1->getLoopDepth() < L2->getLoopDepth();
                           }))
              ? LastLoop
              : nullptr;
 }
 
 static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize,
                                   const Loop &L, ScalarEvolution &SE) {
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&AccessFn);
   if (!AR || !AR->isAffine())

llvm/lib/Analysis/TargetLibraryInfo.cpp

 }
 
 /// Initialize the set of available library functions based on the specified
 /// target triple. This should be carefully written so that a missing target
 /// triple gets a sane set of defaults.
 static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T,
                        ArrayRef<StringLiteral> StandardNames) {
   // Verify that the StandardNames array is in alphabetical order.
-  assert(std::is_sorted(StandardNames.begin(), StandardNames.end(),
-                        [](StringRef LHS, StringRef RHS) {
-                          return LHS < RHS;
-                        }) &&
-         "TargetLibraryInfoImpl function names must be sorted");
+  assert(
+      llvm::is_sorted(StandardNames,
+                      [](StringRef LHS, StringRef RHS) { return LHS < RHS; }) &&
 
   // Set IO unlocked variants as unavailable
   // Set them as available per system below
   TLI.setUnavailable(LibFunc_getchar_unlocked);
   TLI.setUnavailable(LibFunc_putc_unlocked);
   TLI.setUnavailable(LibFunc_putchar_unlocked);
   TLI.setUnavailable(LibFunc_fputc_unlocked);
   TLI.setUnavailable(LibFunc_fgetc_unlocked);

llvm/lib/Bitcode/Writer/ValueEnumerator.cpp

llvm::sort(List, [&](const Entry &L, const Entry &R) {
     // LID and RID are equal, so we have different operands of the same user.
     // Assume operands are added in order for all instructions.
     if (LID <= ID)
       if (!IsGlobalValue) // GlobalValue uses don't get reversed.
         return LU->getOperandNo() < RU->getOperandNo();
     return LU->getOperandNo() > RU->getOperandNo();
   });
 
-  if (std::is_sorted(
-          List.begin(), List.end(),
-          [](const Entry &L, const Entry &R) { return L.second < R.second; }))
+  if (llvm::is_sorted(List, [](const Entry &L, const Entry &R) {
+        return L.second < R.second;
+      }))
     // Order is already correct.
     return;
 
   // Store the shuffle.
   Stack.emplace_back(V, F, List.size());
   assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
   for (size_t I = 0, E = List.size(); I != E; ++I)
     Stack.back().Shuffle[I] = List[I].second;

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

void DebugLocEntry::finalize(const AsmPrinter &AP,
   BufferByteStreamer Streamer = Entry.getStreamer();
   DebugLocDwarfExpression DwarfExpr(AP.getDwarfVersion(), Streamer, TheCU);
   const DbgValueLoc &Value = Values[0];
   if (Value.isFragment()) {
     // Emit all fragments that belong to the same variable and range.
     assert(llvm::all_of(Values, [](DbgValueLoc P) {
           return P.isFragment();
         }) && "all values are expected to be fragments");
-    assert(std::is_sorted(Values.begin(), Values.end()) &&
-           "fragments are expected to be sorted");
+    assert(llvm::is_sorted(Values) && "fragments are expected to be sorted");
 
     for (auto Fragment : Values)
       DwarfDebug::emitDebugLocValue(AP, BT, Fragment, DwarfExpr);
 
   } else {
     assert(Values.size() == 1 && "only fragments may have >1 value");
     DwarfDebug::emitDebugLocValue(AP, BT, Value, DwarfExpr);
   }

llvm/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

#endif
   return Extract;
 }
 
 void MachineIRBuilder::buildSequence(Register Res, ArrayRef<Register> Ops,
                                      ArrayRef<uint64_t> Indices) {
 #ifndef NDEBUG
   assert(Ops.size() == Indices.size() && "incompatible args");
   assert(!Ops.empty() && "invalid trivial sequence");
-  assert(std::is_sorted(Indices.begin(), Indices.end()) &&
+  assert(llvm::is_sorted(Indices) &&
          "sequence offsets must be in ascending order");
 
   assert(getMRI()->getType(Res).isValid() && "invalid operand type");
   for (auto Op : Ops)
     assert(getMRI()->getType(Op).isValid() && "invalid operand type");
 #endif
 
   LLT ResTy = getMRI()->getType(Res);

llvm/lib/Frontend/OpenMP/OMPContext.cpp

LLVM_DEBUG({
     }
   });
 }
 
 /// Return true if \p C0 is a subset of \p C1. Note that both arrays are
 /// expected to be sorted.
 template <typename T> static bool isSubset(ArrayRef<T> C0, ArrayRef<T> C1) {
 #ifdef EXPENSIVE_CHECKS
-  assert(std::is_sorted(C0.begin(), C0.end()) &&
-         std::is_sorted(C1.begin(), C1.end()) && "Expected sorted arrays!");
+  assert(llvm::is_sorted(C0) && llvm::is_sorted(C1) &&
+         "Expected sorted arrays!");
 #endif
   if (C0.size() > C1.size())
     return false;
   auto It0 = C0.begin(), End0 = C0.end();
   auto It1 = C1.begin(), End1 = C1.end();
   while (It0 != End0) {
     if (It1 == End1)
       return false;

llvm/lib/IR/AsmWriter.cpp

llvm::sort(List, [&](const Entry &L, const Entry &R) {
     // LID and RID are equal, so we have different operands of the same user.
     // Assume operands are added in order for all instructions.
     if (GetsReversed)
       if (LID <= ID)
         return LU->getOperandNo() < RU->getOperandNo();
     return LU->getOperandNo() > RU->getOperandNo();
   });
 
-  if (std::is_sorted(
-          List.begin(), List.end(),
-          [](const Entry &L, const Entry &R) { return L.second < R.second; }))
+  if (llvm::is_sorted(List, [](const Entry &L, const Entry &R) {
+        return L.second < R.second;
+      }))
     // Order is already correct.
     return;
 
   // Store the shuffle.
   Stack.emplace_back(V, F, List.size());
   assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
   for (size_t I = 0, E = List.size(); I != E; ++I)
     Stack.back().Shuffle[I] = List[I].second;

llvm/lib/IR/Attributes.cpp

 
 AttributeList
 AttributeList::get(LLVMContext &C,
                    ArrayRef<std::pair<unsigned, Attribute>> Attrs) {
   // If there are no attributes then return a null AttributesList pointer.
   if (Attrs.empty())
     return {};
 
-  assert(std::is_sorted(Attrs.begin(), Attrs.end(),
+  assert(llvm::is_sorted(Attrs,
                          [](const std::pair<unsigned, Attribute> &LHS,
                             const std::pair<unsigned, Attribute> &RHS) {
                            return LHS.first < RHS.first;
-                        }) && "Misordered Attributes list!");
+                         }) &&
+         "Misordered Attributes list!");
   assert(llvm::none_of(Attrs,
                        [](const std::pair<unsigned, Attribute> &Pair) {
                          return Pair.second.hasAttribute(Attribute::None);
                        }) &&
          "Pointless attribute!");
 
   // Create a vector if (unsigned, AttributeSetNode*) pairs from the attributes
   // list.

 
 AttributeList
 AttributeList::get(LLVMContext &C,
                    ArrayRef<std::pair<unsigned, AttributeSet>> Attrs) {
   // If there are no attributes then return a null AttributesList pointer.
   if (Attrs.empty())
     return {};
 
-  assert(std::is_sorted(Attrs.begin(), Attrs.end(),
+  assert(llvm::is_sorted(Attrs,
                          [](const std::pair<unsigned, AttributeSet> &LHS,
                             const std::pair<unsigned, AttributeSet> &RHS) {
                            return LHS.first < RHS.first;
                          }) &&
          "Misordered Attributes list!");
   assert(llvm::none_of(Attrs,
                        [](const std::pair<unsigned, AttributeSet> &Pair) {
                          return !Pair.second.hasAttributes();
                        }) &&
          "Pointless attribute!");
 
   unsigned MaxIndex = Attrs.back().first;
#endif
   AttrSets[Index] = AttributeSet::get(C, Merged);
 
   return getImpl(C, AttrSets);
 }
 
 AttributeList AttributeList::addParamAttribute(LLVMContext &C,
                                                ArrayRef<unsigned> ArgNos,
                                                Attribute A) const {
-  assert(std::is_sorted(ArgNos.begin(), ArgNos.end()));
+  assert(llvm::is_sorted(ArgNos));
 
   SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
   unsigned MaxIndex = attrIdxToArrayIdx(ArgNos.back() + FirstArgIndex);
   if (MaxIndex >= AttrSets.size())
     AttrSets.resize(MaxIndex + 1);
 
   for (unsigned ArgNo : ArgNos) {
     unsigned Index = attrIdxToArrayIdx(ArgNo + FirstArgIndex);

llvm/lib/MC/MCSubtargetInfo.cpp

 static FeatureBitset getFeatures(StringRef CPU, StringRef FS,
                                  ArrayRef<SubtargetSubTypeKV> ProcDesc,
                                  ArrayRef<SubtargetFeatureKV> ProcFeatures) {
   SubtargetFeatures Features(FS);
 
   if (ProcDesc.empty() || ProcFeatures.empty())
     return FeatureBitset();
 
-  assert(std::is_sorted(std::begin(ProcDesc), std::end(ProcDesc)) &&
-         "CPU table is not sorted");
-  assert(std::is_sorted(std::begin(ProcFeatures), std::end(ProcFeatures)) &&
-         "CPU features table is not sorted");
+  assert(llvm::is_sorted(ProcDesc) && "CPU table is not sorted");
+  assert(llvm::is_sorted(ProcFeatures) && "CPU features table is not sorted");
   // Resulting bits
   FeatureBitset Bits;
 
   // Check if help is needed
   if (CPU == "help")
     Help(ProcDesc, ProcFeatures);
 
   // Find CPU entry if CPU name is specified.
for (std::string F : T.getFeatures()) {
     if (F[0] == '-')
       F[0] = '+';
     ::ApplyFeatureFlag(All, F, ProcFeatures);
   }
   return (FeatureBits & All) == Set;
 }
 
 const MCSchedModel &MCSubtargetInfo::getSchedModelForCPU(StringRef CPU) const {
-  assert(std::is_sorted(ProcDesc.begin(), ProcDesc.end()) &&
+  assert(llvm::is_sorted(ProcDesc) &&
          "Processor machine model table is not sorted");
 
   // Find entry
   const SubtargetSubTypeKV *CPUEntry = Find(CPU, ProcDesc);
 
   if (!CPUEntry) {
     if (CPU != "help") // Don't error if the user asked for help.
       errs() << "'" << CPU

llvm/lib/Target/ARM/ARMExpandPseudoInsts.cpp

 
 /// LookupNEONLdSt - Search the NEONLdStTable for information about a NEON
 /// load or store pseudo instruction.
 static const NEONLdStTableEntry *LookupNEONLdSt(unsigned Opcode) {
 #ifndef NDEBUG
   // Make sure the table is sorted.
   static std::atomic<bool> TableChecked(false);
   if (!TableChecked.load(std::memory_order_relaxed)) {
-    assert(std::is_sorted(std::begin(NEONLdStTable), std::end(NEONLdStTable)) &&
-           "NEONLdStTable is not sorted!");
+    assert(llvm::is_sorted(NEONLdStTable) && "NEONLdStTable is not sorted!");
     TableChecked.store(true, std::memory_order_relaxed);
   }
 #endif
 
   auto I = llvm::lower_bound(NEONLdStTable, Opcode);
   if (I != std::end(NEONLdStTable) && I->PseudoOpc == Opcode)
     return I;
   return nullptr;

llvm/lib/Target/ARM/AsmParser/ARMAsmParser.cpp

if (ARMMCRegisterClasses[ARM::DPRRegClassID].contains(
         Kind = k_FPSRegisterListWithVPR;
       else
         Kind = k_SPRRegisterList;
     }
 
     if (Kind == k_RegisterList && Regs.back().second == ARM::APSR)
       Kind = k_RegisterListWithAPSR;
 
-    assert(std::is_sorted(Regs.begin(), Regs.end()) &&
-           "Register list must be sorted by encoding");
+    assert(llvm::is_sorted(Regs) && "Register list must be sorted by encoding");
 
     auto Op = std::make_unique<ARMOperand>(Kind);
     for (const auto &P : Regs)
       Op->Registers.push_back(P.second);
 
     Op->StartLoc = StartLoc;
     Op->EndLoc = EndLoc;
     return Op;

llvm/lib/Target/Mips/MipsCCState.cpp

const char *const LibCalls[] = {
       "ceill",         "copysignl",    "cosl",          "exp2l",
       "expl",          "floorl",       "fmal",          "fmaxl",
       "fmodl",         "log10l",       "log2l",         "logl",
       "nearbyintl",    "powl",         "rintl",         "roundl",
       "sinl",          "sqrtl",        "truncl"};
 
   // Check that LibCalls is sorted alphabetically.
   auto Comp = [](const char *S1, const char *S2) { return strcmp(S1, S2) < 0; };
-  assert(std::is_sorted(std::begin(LibCalls), std::end(LibCalls), Comp));
-  return std::binary_search(std::begin(LibCalls), std::end(LibCalls),
-                            CallSym, Comp);
+  assert(llvm::is_sorted(LibCalls, Comp));
+  return std::binary_search(std::begin(LibCalls), std::end(LibCalls), CallSym,
+                            Comp);
 }
 
 /// This function returns true if Ty is fp128, {f128} or i128 which was
 /// originally a fp128.
 static bool originalTypeIsF128(const Type *Ty, const char *Func) {
   if (Ty->isFP128Ty())
     return true;
 

llvm/lib/Target/X86/X86EvexToVex.cpp

bool EvexToVexInstPass::CompressEvexToVexImpl(MachineInstr &MI) const {
   // and can't be converted to VEX.
   if (Desc.TSFlags & X86II::EVEX_L2)
     return false;
 
 #ifndef NDEBUG
   // Make sure the tables are sorted.
   static std::atomic<bool> TableChecked(false);
   if (!TableChecked.load(std::memory_order_relaxed)) {
-    assert(std::is_sorted(std::begin(X86EvexToVex128CompressTable),
-                          std::end(X86EvexToVex128CompressTable)) &&
+    assert(llvm::is_sorted(X86EvexToVex128CompressTable) &&
            "X86EvexToVex128CompressTable is not sorted!");
-    assert(std::is_sorted(std::begin(X86EvexToVex256CompressTable),
-                          std::end(X86EvexToVex256CompressTable)) &&
+    assert(llvm::is_sorted(X86EvexToVex256CompressTable) &&
            "X86EvexToVex256CompressTable is not sorted!");
     TableChecked.store(true, std::memory_order_relaxed);
   }
 #endif
 
   // Use the VEX.L bit to select the 128 or 256-bit table.
   ArrayRef<X86EvexToVexCompressTableEntry> Table =
     (Desc.TSFlags & X86II::VEX_L) ? makeArrayRef(X86EvexToVex256CompressTable)

llvm/lib/Target/X86/X86ISelLowering.cpp

static const MCPhysReg XMMArgRegs64Bit[] = {
     X86::XMM0, X86::XMM1, X86::XMM2, X86::XMM3,
     X86::XMM4, X86::XMM5, X86::XMM6, X86::XMM7
   };
   return makeArrayRef(std::begin(XMMArgRegs64Bit), std::end(XMMArgRegs64Bit));
 }
 
 #ifndef NDEBUG
 static bool isSortedByValueNo(ArrayRef<CCValAssign> ArgLocs) {
-  return std::is_sorted(ArgLocs.begin(), ArgLocs.end(),
-                        [](const CCValAssign &A, const CCValAssign &B) -> bool {
-                          return A.getValNo() < B.getValNo();
-                        });
+  return llvm::is_sorted(
+      ArgLocs, [](const CCValAssign &A, const CCValAssign &B) -> bool {
 }
 #endif
 
 SDValue X86TargetLowering::LowerFormalArguments(
     SDValue Chain, CallingConv::ID CallConv, bool isVarArg,
     const SmallVectorImpl<ISD::InputArg> &Ins, const SDLoc &dl,
     SelectionDAG &DAG, SmallVectorImpl<SDValue> &InVals) const {
   MachineFunction &MF = DAG.getMachineFunction();

llvm/lib/Target/X86/X86InstrFMA3Info.cpp

static const X86InstrFMA3Group RoundGroups[] = {
   FMA3GROUP_PACKED_AVX512_ROUND(VFNMSUB, rb, 0)
   FMA3GROUP_SCALAR_AVX512_ROUND(VFNMSUB, rb, X86InstrFMA3Group::Intrinsic)
 };
 
 static void verifyTables() {
 #ifndef NDEBUG
   static std::atomic<bool> TableChecked(false);
   if (!TableChecked.load(std::memory_order_relaxed)) {
-    assert(std::is_sorted(std::begin(Groups), std::end(Groups)) &&
-           std::is_sorted(std::begin(RoundGroups), std::end(RoundGroups)) &&
-           std::is_sorted(std::begin(BroadcastGroups),
-                          std::end(BroadcastGroups)) &&
-           "FMA3 tables not sorted!");
+    assert(llvm::is_sorted(Groups) && llvm::is_sorted(RoundGroups) &&
+           llvm::is_sorted(BroadcastGroups) && "FMA3 tables not sorted!");
     TableChecked.store(true, std::memory_order_relaxed);
   }
 #endif
 }
 
 /// Returns a reference to a group of FMA3 opcodes to where the given
 /// \p Opcode is included. If the given \p Opcode is not recognized as FMA3
 /// and not included into any FMA3 group, then nullptr is returned.

llvm/lib/Target/X86/X86InstrFoldTables.cpp

 };
 
 static const X86MemoryFoldTableEntry *
 lookupFoldTableImpl(ArrayRef<X86MemoryFoldTableEntry> Table, unsigned RegOp) {
 #ifndef NDEBUG
   // Make sure the tables are sorted.
   static std::atomic<bool> FoldTablesChecked(false);
   if (!FoldTablesChecked.load(std::memory_order_relaxed)) {
-    assert(std::is_sorted(std::begin(MemoryFoldTable2Addr),
-                          std::end(MemoryFoldTable2Addr)) &&
+    assert(llvm::is_sorted(MemoryFoldTable2Addr) &&
            std::adjacent_find(std::begin(MemoryFoldTable2Addr),
                               std::end(MemoryFoldTable2Addr)) ==
                std::end(MemoryFoldTable2Addr) &&
            "MemoryFoldTable2Addr is not sorted and unique!");
-    assert(std::is_sorted(std::begin(MemoryFoldTable0),
-                          std::end(MemoryFoldTable0)) &&
+    assert(llvm::is_sorted(MemoryFoldTable0) &&
            std::adjacent_find(std::begin(MemoryFoldTable0),
                               std::end(MemoryFoldTable0)) ==
                std::end(MemoryFoldTable0) &&
            "MemoryFoldTable0 is not sorted and unique!");
-    assert(std::is_sorted(std::begin(MemoryFoldTable1),
-                          std::end(MemoryFoldTable1)) &&
+    assert(llvm::is_sorted(MemoryFoldTable1) &&
            std::adjacent_find(std::begin(MemoryFoldTable1),
                               std::end(MemoryFoldTable1)) ==
                std::end(MemoryFoldTable1) &&
            "MemoryFoldTable1 is not sorted and unique!");
-    assert(std::is_sorted(std::begin(MemoryFoldTable2),
-                          std::end(MemoryFoldTable2)) &&
+    assert(llvm::is_sorted(MemoryFoldTable2) &&
            std::adjacent_find(std::begin(MemoryFoldTable2),
                               std::end(MemoryFoldTable2)) ==
                std::end(MemoryFoldTable2) &&
            "MemoryFoldTable2 is not sorted and unique!");
-    assert(std::is_sorted(std::begin(MemoryFoldTable3),
-                          std::end(MemoryFoldTable3)) &&
+    assert(llvm::is_sorted(MemoryFoldTable3) &&
            std::adjacent_find(std::begin(MemoryFoldTable3),
                               std::end(MemoryFoldTable3)) ==
                std::end(MemoryFoldTable3) &&
            "MemoryFoldTable3 is not sorted and unique!");
-    assert(std::is_sorted(std::begin(MemoryFoldTable4),
-                          std::end(MemoryFoldTable4)) &&
+    assert(llvm::is_sorted(MemoryFoldTable4) &&
            std::adjacent_find(std::begin(MemoryFoldTable4),
                               std::end(MemoryFoldTable4)) ==
                std::end(MemoryFoldTable4) &&
            "MemoryFoldTable4 is not sorted and unique!");
-    assert(std::is_sorted(std::begin(BroadcastFoldTable2),
-                          std::end(BroadcastFoldTable2)) &&
+    assert(llvm::is_sorted(BroadcastFoldTable2) &&
            std::adjacent_find(std::begin(BroadcastFoldTable2),
                               std::end(BroadcastFoldTable2)) ==
                std::end(BroadcastFoldTable2) &&
            "BroadcastFoldTable2 is not sorted and unique!");
-    assert(std::is_sorted(std::begin(BroadcastFoldTable3),
-                          std::end(BroadcastFoldTable3)) &&
+    assert(llvm::is_sorted(BroadcastFoldTable3) &&
            std::adjacent_find(std::begin(BroadcastFoldTable3),
                               std::end(BroadcastFoldTable3)) ==
                std::end(BroadcastFoldTable3) &&
            "BroadcastFoldTable3 is not sorted and unique!");
     FoldTablesChecked.store(true, std::memory_order_relaxed);
   }
 #endif
 
   const X86MemoryFoldTableEntry *Data = llvm::lower_bound(Table, RegOp);
   if (Data != Table.end() && Data->KeyOp == RegOp &&
       !(Data->Flags & TB_NO_FORWARD))

llvm/lib/Target/X86/X86IntrinsicsInfo.h

const IntrinsicData *Data = std::lower_bound(std::begin(IntrinsicsWithoutChain),
                                                std::end(IntrinsicsWithoutChain),
                                                IntNo);
   if (Data != std::end(IntrinsicsWithoutChain) && Data->Id == IntNo)
     return Data;
   return nullptr;
 }
 
 static void verifyIntrinsicTables() {
-  assert(std::is_sorted(std::begin(IntrinsicsWithoutChain),
-                        std::end(IntrinsicsWithoutChain)) &&
-         std::is_sorted(std::begin(IntrinsicsWithChain),
-                        std::end(IntrinsicsWithChain)) &&
+  assert(llvm::is_sorted(IntrinsicsWithoutChain) &&
+         llvm::is_sorted(IntrinsicsWithChain) &&
          "Intrinsic data tables should be sorted by Intrinsic ID");
   assert((std::adjacent_find(std::begin(IntrinsicsWithoutChain),
                              std::end(IntrinsicsWithoutChain)) ==
           std::end(IntrinsicsWithoutChain)) &&
          (std::adjacent_find(std::begin(IntrinsicsWithChain),
                              std::end(IntrinsicsWithChain)) ==
           std::end(IntrinsicsWithChain)) &&
          "Intrinsic data tables should have unique entries");
 }
 } // End llvm namespace
 
 #endif

llvm/lib/Transforms/IPO/CalledValuePropagation.cpp

bool operator()(const Function *LHS, const Function *RHS) const {
       return LHS->getName() < RHS->getName();
     }
   };
 
   CVPLatticeVal() : LatticeState(Undefined) {}
   CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
   CVPLatticeVal(std::vector<Function *> &&Functions)
       : LatticeState(FunctionSet), Functions(std::move(Functions)) {
-    assert(std::is_sorted(this->Functions.begin(), this->Functions.end(),
-                          Compare()));
+    assert(llvm::is_sorted(this->Functions, Compare()));
   }
 
   /// Get a reference to the functions held by this lattice value. The number
   /// of functions will be zero for states other than FunctionSet.
   const std::vector<Function *> &getFunctions() const {
     return Functions;
   }
 

llvm/tools/llvm-exegesis/lib/Target.cpp

 }
 
 static_assert(std::is_pod<PfmCountersInfo>::value,
               "We shouldn't have dynamic initialization here");
 const PfmCountersInfo PfmCountersInfo::Default = {nullptr, nullptr, nullptr,
                                                   0u};
 
 const PfmCountersInfo &ExegesisTarget::getPfmCounters(StringRef CpuName) const {
-  assert(std::is_sorted(
-             CpuPfmCounters.begin(), CpuPfmCounters.end(),
+  assert(llvm::is_sorted(
+             CpuPfmCounters,
              [](const CpuAndPfmCounters &LHS, const CpuAndPfmCounters &RHS) {
                return strcmp(LHS.CpuName, RHS.CpuName) < 0;
              }) &&
          "CpuPfmCounters table is not sorted");
 
   // Find entry
   auto Found =
       std::lower_bound(CpuPfmCounters.begin(), CpuPfmCounters.end(), CpuName);

llvm/tools/llvm-objcopy/ELF/Object.cpp

static void orderSegments(std::vector<Segment *> &Segments) {
   llvm::stable_sort(Segments, compareSegmentsByOffset);
 }
 
 // This function finds a consistent layout for a list of segments starting from
 // an Offset. It assumes that Segments have been sorted by orderSegments and
 // returns an Offset one past the end of the last segment.
 static uint64_t layoutSegments(std::vector<Segment *> &Segments,
                                uint64_t Offset) {
-  assert(std::is_sorted(std::begin(Segments), std::end(Segments),
-                        compareSegmentsByOffset));
+  assert(llvm::is_sorted(Segments, compareSegmentsByOffset));
   // The only way a segment should move is if a section was between two
   // segments and that section was removed. If that section isn't in a segment
   // then it's acceptable, but not ideal, to simply move it to after the
   // segments. So we can simply layout segments one after the other accounting
   // for alignment.
   for (Segment *Seg : Segments) {
     // We assume that segments have been ordered by OriginalOffset and Index
     // such that a parent segment will always come before a child segment in

llvm/tools/llvm-objcopy/MachO/MachOLayoutBuilder.cpp

for (auto &Symbol : O.SymTable.Symbols)
     Symbol->Index = Index++;
 }
 
 // Updates the index and the number of local/external/undefined symbols.
 void MachOLayoutBuilder::updateDySymTab(MachO::macho_load_command &MLC) {
   assert(MLC.load_command_data.cmd == MachO::LC_DYSYMTAB);
   // Make sure that nlist entries in the symbol table are sorted by the those
   // types. The order is: local < defined external < undefined external.
-  assert(std::is_sorted(O.SymTable.Symbols.begin(), O.SymTable.Symbols.end(),
+  assert(llvm::is_sorted(O.SymTable.Symbols,
                          [](const std::unique_ptr<SymbolEntry> &A,
                             const std::unique_ptr<SymbolEntry> &B) {
-                          bool AL = A->isLocalSymbol(), BL = B->isLocalSymbol();
+                           bool AL = A->isLocalSymbol(),
+                                BL = B->isLocalSymbol();
                            if (AL != BL)
                              return AL;
                            return !AL && !A->isUndefinedSymbol() &&
-                                         B->isUndefinedSymbol();
                          }) &&
          "Symbols are not sorted by their types.");
 
   uint32_t NumLocalSymbols = 0;
   auto Iter = O.SymTable.Symbols.begin();
   auto End = O.SymTable.Symbols.end();
   for (; Iter != End; ++Iter) {
     if ((*Iter)->isExternalSymbol())
       break;

llvm/unittests/ADT/SimpleIListTest.cpp

for (bool IsL1LHS : {false, true}) {
     L2.push_back(Ns[5]);
     L2.push_back(Ns[6]);
     L2.push_back(Ns[7]);
     L2.push_back(Ns[9]);
 
     // Check setup.
     EXPECT_EQ(4u, L1.size());
     EXPECT_EQ(6u, L2.size());
-    EXPECT_TRUE(std::is_sorted(L1.begin(), L1.end()));
-    EXPECT_TRUE(std::is_sorted(L2.begin(), L2.end()));
+    EXPECT_TRUE(llvm::is_sorted(L1));
+    EXPECT_TRUE(llvm::is_sorted(L2));
 
     // Merge.
     auto &LHS = IsL1LHS ? L1 : L2;
     auto &RHS = IsL1LHS ? L2 : L1;
     LHS.merge(RHS);
     EXPECT_TRUE(RHS.empty());
     EXPECT_FALSE(LHS.empty());
-    EXPECT_TRUE(std::is_sorted(LHS.begin(), LHS.end()));
+    EXPECT_TRUE(llvm::is_sorted(LHS));
     auto I = LHS.begin();
     for (Node &N : Ns)
       EXPECT_EQ(&N, &*I++);
     EXPECT_EQ(LHS.end(), I);
   }
 }
 
 TEST(SimpleIListTest, mergeIsStable) {
auto setup = [&]() {
 
     // Fill L2.
     L2.push_back(Ns[1]);
     L2.push_back(Ns[2]);
 
     // Check setup.
     EXPECT_EQ(3u, L1.size());
     EXPECT_EQ(2u, L2.size());
-    EXPECT_TRUE(std::is_sorted(L1.begin(), L1.end(), makeFalse));
-    EXPECT_TRUE(std::is_sorted(L2.begin(), L2.end(), makeFalse));
+    EXPECT_TRUE(llvm::is_sorted(L1, makeFalse));
+    EXPECT_TRUE(llvm::is_sorted(L2, makeFalse));
   };
 
   // Merge.  Should be stable.
   setup();
   L1.merge(L2, makeFalse);
   EXPECT_TRUE(L2.empty());
   EXPECT_FALSE(L1.empty());
-  EXPECT_TRUE(std::is_sorted(L1.begin(), L1.end(), makeFalse));
+  EXPECT_TRUE(llvm::is_sorted(L1, makeFalse));
   auto I = L1.begin();
   EXPECT_EQ(&Ns[0], &*I++);
   EXPECT_EQ(&Ns[3], &*I++);
   EXPECT_EQ(&Ns[4], &*I++);
   EXPECT_EQ(&Ns[1], &*I++);
   EXPECT_EQ(&Ns[2], &*I++);
   EXPECT_EQ(L1.end(), I);
 
   // Merge the other way.  Should be stable.
   L1.clear();
   setup();
   L2.merge(L1, makeFalse);
   EXPECT_TRUE(L1.empty());
   EXPECT_FALSE(L2.empty());
-  EXPECT_TRUE(std::is_sorted(L2.begin(), L2.end(), makeFalse));
+  EXPECT_TRUE(llvm::is_sorted(L2, makeFalse));
   I = L2.begin();
   EXPECT_EQ(&Ns[1], &*I++);
   EXPECT_EQ(&Ns[2], &*I++);
   EXPECT_EQ(&Ns[0], &*I++);
   EXPECT_EQ(&Ns[3], &*I++);
   EXPECT_EQ(&Ns[4], &*I++);
   EXPECT_EQ(L2.end(), I);
 }
 
 TEST(SimpleIListTest, mergeEmpty) {
   for (bool IsL1LHS : {false, true}) {
     simple_ilist<Node> L1, L2;
     Node Ns[4];
 
     // Fill L1.
     L1.push_back(Ns[0]);
     L1.push_back(Ns[1]);
     L1.push_back(Ns[2]);
     L1.push_back(Ns[3]);
 
     // Check setup.
     EXPECT_EQ(4u, L1.size());
     EXPECT_TRUE(L2.empty());
-    EXPECT_TRUE(std::is_sorted(L1.begin(), L1.end()));
+    EXPECT_TRUE(llvm::is_sorted(L1));
 
     // Merge.
     auto &LHS = IsL1LHS ? L1 : L2;
     auto &RHS = IsL1LHS ? L2 : L1;
     LHS.merge(RHS);
     EXPECT_TRUE(RHS.empty());
     EXPECT_FALSE(LHS.empty());
-    EXPECT_TRUE(std::is_sorted(LHS.begin(), LHS.end()));
+    EXPECT_TRUE(llvm::is_sorted(LHS));
     auto I = LHS.begin();
     for (Node &N : Ns)
       EXPECT_EQ(&N, &*I++);
     EXPECT_EQ(LHS.end(), I);
   }
 }
 
 TEST(SimpleIListTest, mergeBothEmpty) {
   simple_ilist<Node> L1, L2;
   L1.merge(L2);
   EXPECT_TRUE(L1.empty());
   EXPECT_TRUE(L2.empty());
 }
 
 TEST(SimpleIListTest, sort) {
   simple_ilist<Node> L;
   Node Ns[10];
 
   // Fill L.
   for (int I : {3, 4, 0, 8, 1, 2, 6, 7, 9, 5})
     L.push_back(Ns[I]);
 
   // Check setup.
   EXPECT_EQ(10u, L.size());
-  EXPECT_FALSE(std::is_sorted(L.begin(), L.end()));
+  EXPECT_FALSE(llvm::is_sorted(L));
 
   // Sort.
   L.sort();
-  EXPECT_TRUE(std::is_sorted(L.begin(), L.end()));
+  EXPECT_TRUE(llvm::is_sorted(L));
   auto I = L.begin();
   for (Node &N : Ns)
     EXPECT_EQ(&N, &*I++);
   EXPECT_EQ(L.end(), I);
 }
 
 TEST(SimpleIListTest, sortIsStable) {
   simple_ilist<Node> L;
   Node Ns[10];
 
   // Compare such that nodes are partitioned but not fully sorted.
   auto partition = [&](const Node &N) { return &N >= &Ns[5]; };
   auto compare = [&](const Node &L, const Node &R) {
     return partition(L) < partition(R);
   };
 
   // Fill L.
   for (int I : {3, 4, 7, 8, 1, 2, 6, 0, 9, 5})
     L.push_back(Ns[I]);
 
   // Check setup.
   EXPECT_EQ(10u, L.size());
-  EXPECT_FALSE(std::is_sorted(L.begin(), L.end(), compare));
+  EXPECT_FALSE(llvm::is_sorted(L, compare));
 
   // Sort.
   L.sort(compare);
-  EXPECT_TRUE(std::is_sorted(L.begin(), L.end(), compare));
+  EXPECT_TRUE(llvm::is_sorted(L, compare));
   auto I = L.begin();
   for (int O : {3, 4, 1, 2, 0})
     EXPECT_EQ(&Ns[O], &*I++);
   for (int O : {7, 8, 6, 9, 5})
     EXPECT_EQ(&Ns[O], &*I++);
   EXPECT_EQ(L.end(), I);
 }
 

llvm/unittests/Support/ParallelTest.cpp

 TEST(Parallel, sort) {
   std::mt19937 randEngine;
   std::uniform_int_distribution<uint32_t> dist;
 
   for (auto &i : array)
     i = dist(randEngine);
 
   sort(parallel::par, std::begin(array), std::end(array));
-  ASSERT_TRUE(std::is_sorted(std::begin(array), std::end(array)));
+  ASSERT_TRUE(llvm::is_sorted(array));
 }
 
 TEST(Parallel, parallel_for) {
   // We need to test the case with a TaskSize > 1. We are white-box testing
   // here. The TaskSize is calculated as (End - Begin) / 1024 at the time of
   // writing.
   uint32_t range[2050];
   std::fill(range, range + 2050, 1);