[Transforms] Change std::sort to llvm::sort in response to r327219

[mgrang]

Summary

r327219 added wrappers to std::sort which randomly shuffle the container before sorting.
This will help in uncovering non-determinism caused due to undefined sorting
order of objects having the same key.

To make use of that infrastructure we need to invoke llvm::sort instead of std::sort.

Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort.
Refer the comments section in D44363 for a list of all the required patches.

[mgrang]

Ping for reviews please.

[ruiu]

LGTM

This is a mechanical change to replace std::sort with llvm::sort.

llvm/trunk/lib/Transforms/Coroutines/CoroFrame.cpp

class BlockToIndexMapping {
   SmallVector<BasicBlock *, SmallVectorThreshold> V;
 
 public:
   size_t size() const { return V.size(); }
 
   BlockToIndexMapping(Function &F) {
     for (BasicBlock &BB : F)
       V.push_back(&BB);
-    std::sort(V.begin(), V.end());
+    llvm::sort(V.begin(), V.end());
   }
 
   size_t blockToIndex(BasicBlock *BB) const {
     auto *I = std::lower_bound(V.begin(), V.end(), BB);
     assert(I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block");
     return I - V.begin();
   }
 

llvm/trunk/lib/Transforms/IPO/LowerTypeTests.cpp

for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
     unsigned MaxIndex = 0;
     for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
          MI != GlobalClasses.member_end(); ++MI) {
       if ((*MI).is<Metadata *>())
         MaxIndex = std::max(MaxIndex, TypeIdInfo[MI->get<Metadata *>()].Index);
     }
     Sets.emplace_back(I, MaxIndex);
   }
-  std::sort(Sets.begin(), Sets.end(),
+  llvm::sort(Sets.begin(), Sets.end(),
              [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1,
                 const std::pair<GlobalClassesTy::iterator, unsigned> &S2) {
                return S1.second < S2.second;
              });
 
   // For each disjoint set we found...
   for (const auto &S : Sets) {
     // Build the list of type identifiers in this disjoint set.
     std::vector<Metadata *> TypeIds;
     std::vector<GlobalTypeMember *> Globals;
     std::vector<ICallBranchFunnel *> ICallBranchFunnels;
     for (GlobalClassesTy::member_iterator MI =
              GlobalClasses.member_begin(S.first);
          MI != GlobalClasses.member_end(); ++MI) {
       if (MI->is<Metadata *>())
         TypeIds.push_back(MI->get<Metadata *>());
       else if (MI->is<GlobalTypeMember *>())
         Globals.push_back(MI->get<GlobalTypeMember *>());
       else
         ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>());
     }
 
     // Order type identifiers by global index for determinism. This ordering is
     // stable as there is a one-to-one mapping between metadata and indices.
-    std::sort(TypeIds.begin(), TypeIds.end(), [&](Metadata *M1, Metadata *M2) {
+    llvm::sort(TypeIds.begin(), TypeIds.end(), [&](Metadata *M1, Metadata *M2) {
       return TypeIdInfo[M1].Index < TypeIdInfo[M2].Index;
     });
 
     // Build bitsets for this disjoint set.
     buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
   }
 
   allocateByteArrays();

llvm/trunk/lib/Transforms/IPO/SampleProfile.cpp

SampleProfileLoader::findIndirectCallFunctionSamples(
   if (const FunctionSamplesMap *M = FS->findFunctionSamplesMapAt(LineLocation(
           FunctionSamples::getOffset(DIL), DIL->getBaseDiscriminator()))) {
     if (M->empty())
       return R;
     for (const auto &NameFS : *M) {
       Sum += NameFS.second.getEntrySamples();
       R.push_back(&NameFS.second);
     }
-    std::sort(R.begin(), R.end(),
+    llvm::sort(R.begin(), R.end(),
                [](const FunctionSamples *L, const FunctionSamples *R) {
                  return L->getEntrySamples() > R->getEntrySamples();
                });
   }
   return R;
 }
 
 /// \brief Get the FunctionSamples for an instruction.
 ///
 /// The FunctionSamples of an instruction \p Inst is the inlined instance
 /// in which that instruction is coming from. We traverse the inline stack

 }
 
 /// Returns the sorted CallTargetMap \p M by count in descending order.
 static SmallVector<InstrProfValueData, 2> SortCallTargets(
     const SampleRecord::CallTargetMap &M) {
   SmallVector<InstrProfValueData, 2> R;
   for (auto I = M.begin(); I != M.end(); ++I)
     R.push_back({Function::getGUID(I->getKey()), I->getValue()});
-  std::sort(R.begin(), R.end(),
+  llvm::sort(R.begin(), R.end(),
              [](const InstrProfValueData &L, const InstrProfValueData &R) {
                if (L.Count == R.Count)
                  return L.Value > R.Value;
                else
                  return L.Count > R.Count;
              });
   return R;
 }
 
 /// \brief Propagate weights into edges
 ///
 /// The following rules are applied to every block BB in the CFG:
 ///
 /// - If BB has a single predecessor/successor, then the weight

llvm/trunk/lib/Transforms/Instrumentation/GCOVProfiling.cpp

void writeOut() {
         Len += I.second.length();
         SortedLinesByFile.push_back(&I);
       }
 
       writeBytes(LinesTag, 4);
       write(Len);
       write(Number);
 
-      std::sort(
+      llvm::sort(
           SortedLinesByFile.begin(), SortedLinesByFile.end(),
           [](StringMapEntry<GCOVLines> *LHS, StringMapEntry<GCOVLines> *RHS) {
             return LHS->getKey() < RHS->getKey();
           });
       for (auto &I : SortedLinesByFile)
         I->getValue().writeOut();
       write(0);
       write(0);

llvm/trunk/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
       for (auto It : SI->cases()) {
         Constant *C = It.getCaseValue();
         if (C->getType()->getScalarSizeInBits() <
             Int64Ty->getScalarSizeInBits())
           C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
         Initializers.push_back(C);
       }
-      std::sort(Initializers.begin() + 2, Initializers.end(),
+      llvm::sort(Initializers.begin() + 2, Initializers.end(),
                  [](const Constant *A, const Constant *B) {
                    return cast<ConstantInt>(A)->getLimitedValue() <
                           cast<ConstantInt>(B)->getLimitedValue();
                  });
       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
       GlobalVariable *GV = new GlobalVariable(
           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
           ConstantArray::get(ArrayOfInt64Ty, Initializers),
           "__sancov_gen_cov_switch_values");
       IRB.CreateCall(SanCovTraceSwitchFunction,
                      {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
     }

llvm/trunk/lib/Transforms/Scalar/ConstantHoisting.cpp

void ConstantHoistingPass::findAndMakeBaseConstant(
   }
   ConstantVec.push_back(std::move(ConstInfo));
 }
 
 /// \brief Finds and combines constant candidates that can be easily
 /// rematerialized with an add from a common base constant.
 void ConstantHoistingPass::findBaseConstants() {
   // Sort the constants by value and type. This invalidates the mapping!
-  std::sort(ConstCandVec.begin(), ConstCandVec.end(),
+  llvm::sort(ConstCandVec.begin(), ConstCandVec.end(),
              [](const ConstantCandidate &LHS, const ConstantCandidate &RHS) {
     if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
       return LHS.ConstInt->getType()->getBitWidth() <
              RHS.ConstInt->getType()->getBitWidth();
     return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
   });
 
   // Simple linear scan through the sorted constant candidate vector for viable
   // merge candidates.

llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp

void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
     std::vector<VNType> Ranks;
     for (const auto &Entry : Map) {
       Ranks.push_back(Entry.first);
     }
 
     // TODO: Remove fully-redundant expressions.
     // Get instruction from the Map, assume that all the Instructions
     // with same VNs have same rank (this is an approximation).
-    std::sort(Ranks.begin(), Ranks.end(),
+    llvm::sort(Ranks.begin(), Ranks.end(),
                [this, &Map](const VNType &r1, const VNType &r2) {
                  return (rank(*Map.lookup(r1).begin()) <
                          rank(*Map.lookup(r2).begin()));
                });
 
     // - Sort VNs according to their rank, and start with lowest ranked VN
     // - Take a VN and for each instruction with same VN
     //   - Find the dominance frontier in the inverse graph (PDF)
     //   - Insert the chi-node at PDF
     // - Remove the chi-nodes with missing entries
     // - Remove values from CHI-nodes which do not truly flow out, e.g.,
     //   modified along the path.

llvm/trunk/lib/Transforms/Scalar/GVNSink.cpp

 public:
   ModelledPHI() = default;
 
   ModelledPHI(const PHINode *PN) {
     // BasicBlock comes first so we sort by basic block pointer order, then by value pointer order.
     SmallVector<std::pair<BasicBlock *, Value *>, 4> Ops;
     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I)
       Ops.push_back({PN->getIncomingBlock(I), PN->getIncomingValue(I)});
-    std::sort(Ops.begin(), Ops.end());
+    llvm::sort(Ops.begin(), Ops.end());
     for (auto &P : Ops) {
       Blocks.push_back(P.first);
       Values.push_back(P.second);
     }
   }
 
   /// Create a dummy ModelledPHI that will compare unequal to any other ModelledPHI
   /// without the same ID.
InstructionUseExpr(Instruction *I, ArrayRecycler<Value *> &R,
                      BumpPtrAllocator &A)
       : GVNExpression::BasicExpression(I->getNumUses()) {
     allocateOperands(R, A);
     setOpcode(I->getOpcode());
     setType(I->getType());
 
     for (auto &U : I->uses())
       op_push_back(U.getUser());
-    std::sort(op_begin(), op_end());
+    llvm::sort(op_begin(), op_end());
   }
 
   void setMemoryUseOrder(unsigned MUO) { MemoryUseOrder = MUO; }
   void setVolatile(bool V) { Volatile = V; }
 
   hash_code getHashValue() const override {
     return hash_combine(GVNExpression::BasicExpression::getHashValue(),
                         MemoryUseOrder, Volatile);
for (auto *B : predecessors(BBEnd)) {
     auto *T = B->getTerminator();
     if (isa<BranchInst>(T) || isa<SwitchInst>(T))
       Preds.push_back(B);
     else
       return 0;
   }
   if (Preds.size() < 2)
     return 0;
-  std::sort(Preds.begin(), Preds.end());
+  llvm::sort(Preds.begin(), Preds.end());
 
   unsigned NumOrigPreds = Preds.size();
   // We can only sink instructions through unconditional branches.
   for (auto I = Preds.begin(); I != Preds.end();) {
     if ((*I)->getTerminator()->getNumSuccessors() != 1)
       I = Preds.erase(I);
     else
       ++I;

llvm/trunk/lib/Transforms/Scalar/GuardWidening.cpp

if (CurrentChecks.size() < 3) {
       RangeChecksOut.insert(RangeChecksOut.end(), CurrentChecks.begin(),
                             CurrentChecks.end());
       continue;
     }
 
     // CurrentChecks.size() will typically be 3 here, but so far there has been
     // no need to hard-code that fact.
 
-    std::sort(CurrentChecks.begin(), CurrentChecks.end(),
+    llvm::sort(CurrentChecks.begin(), CurrentChecks.end(),
                [&](const GuardWideningImpl::RangeCheck &LHS,
                    const GuardWideningImpl::RangeCheck &RHS) {
       return LHS.getOffsetValue().slt(RHS.getOffsetValue());
     });
 
     // Note: std::sort should not invalidate the ChecksStart iterator.
 
     ConstantInt *MinOffset = CurrentChecks.front().getOffset(),
                 *MaxOffset = CurrentChecks.back().getOffset();
 

llvm/trunk/lib/Transforms/Scalar/LoopSink.cpp

if (BBsToSinkInto.empty())
     return false;
 
   // Copy the final BBs into a vector and sort them using the total ordering
   // of the loop block numbers as iterating the set doesn't give a useful
   // order. No need to stable sort as the block numbers are a total ordering.
   SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
   SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(),
                              BBsToSinkInto.end());
-  std::sort(SortedBBsToSinkInto.begin(), SortedBBsToSinkInto.end(),
+  llvm::sort(SortedBBsToSinkInto.begin(), SortedBBsToSinkInto.end(),
              [&](BasicBlock *A, BasicBlock *B) {
                return *LoopBlockNumber.find(A) < *LoopBlockNumber.find(B);
              });
 
   BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
   // FIXME: Optimize the efficiency for cloned value replacement. The current
   //        implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
   for (BasicBlock *N : SortedBBsToSinkInto) {
     if (N == MoveBB)
       continue;
     // Clone I and replace its uses.

llvm/trunk/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 #endif
 
 /// Test whether this use as a formula which has the same registers as the given
 /// formula.
 bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const {
   SmallVector<const SCEV *, 4> Key = F.BaseRegs;
   if (F.ScaledReg) Key.push_back(F.ScaledReg);
   // Unstable sort by host order ok, because this is only used for uniquifying.
-  std::sort(Key.begin(), Key.end());
+  llvm::sort(Key.begin(), Key.end());
   return Uniquifier.count(Key);
 }
 
 /// The function returns a probability of selecting formula without Reg.
 float LSRUse::getNotSelectedProbability(const SCEV *Reg) const {
   unsigned FNum = 0;
   for (const Formula &F : Formulae)
     if (F.referencesReg(Reg))
       FNum++;
   return ((float)(Formulae.size() - FNum)) / Formulae.size();
 }
 
 /// If the given formula has not yet been inserted, add it to the list, and
 /// return true. Return false otherwise.  The formula must be in canonical form.
 bool LSRUse::InsertFormula(const Formula &F, const Loop &L) {
   assert(F.isCanonical(L) && "Invalid canonical representation");
 
   if (!Formulae.empty() && RigidFormula)
     return false;
 
   SmallVector<const SCEV *, 4> Key = F.BaseRegs;
   if (F.ScaledReg) Key.push_back(F.ScaledReg);
   // Unstable sort by host order ok, because this is only used for uniquifying.
-  std::sort(Key.begin(), Key.end());
+  llvm::sort(Key.begin(), Key.end());
 
   if (!Uniquifier.insert(Key).second)
     return false;
 
   // Using a register to hold the value of 0 is not profitable.
   assert((!F.ScaledReg || !F.ScaledReg->isZero()) &&
          "Zero allocated in a scaled register!");
 #ifndef NDEBUG
for (size_t FIdx = 0, NumForms = LU.Formulae.size();
           if (RegUses.isRegUsedByUsesOtherThan(Reg, LUIdx))
             Key.push_back(Reg);
         }
         if (F.ScaledReg &&
             RegUses.isRegUsedByUsesOtherThan(F.ScaledReg, LUIdx))
           Key.push_back(F.ScaledReg);
         // Unstable sort by host order ok, because this is only used for
         // uniquifying.
-        std::sort(Key.begin(), Key.end());
+        llvm::sort(Key.begin(), Key.end());
 
         std::pair<BestFormulaeTy::const_iterator, bool> P =
           BestFormulae.insert(std::make_pair(Key, FIdx));
         if (P.second)
           continue;
 
         Formula &Best = LU.Formulae[P.first->second];
 

llvm/trunk/lib/Transforms/Scalar/MergeICmps.cpp

BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi)
   EntryBlock_ = Comparisons[0].BB;
   Comparisons_ = std::move(Comparisons);
 #ifdef MERGEICMPS_DOT_ON
   errs() << "BEFORE REORDERING:\n\n";
   dump();
 #endif  // MERGEICMPS_DOT_ON
   // Reorder blocks by LHS. We can do that without changing the
   // semantics because we are only accessing dereferencable memory.
-  std::sort(Comparisons_.begin(), Comparisons_.end(),
+  llvm::sort(Comparisons_.begin(), Comparisons_.end(),
              [](const BCECmpBlock &a, const BCECmpBlock &b) {
                return a.Lhs() < b.Lhs();
              });
 #ifdef MERGEICMPS_DOT_ON
   errs() << "AFTER REORDERING:\n\n";
   dump();
 #endif  // MERGEICMPS_DOT_ON
 }
 
 #ifdef MERGEICMPS_DOT_ON
 void BCECmpChain::dump() const {

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

static bool isCopyOfAPHI(const Value *V) {
   auto *CO = getCopyOf(V);
   return CO && isa<PHINode>(CO);
 }
 
 // Sort PHI Operands into a canonical order.  What we use here is an RPO
 // order. The BlockInstRange numbers are generated in an RPO walk of the basic
 // blocks.
 void NewGVN::sortPHIOps(MutableArrayRef<ValPair> Ops) const {
-  std::sort(Ops.begin(), Ops.end(), [&](const ValPair &P1, const ValPair &P2) {
+  llvm::sort(Ops.begin(), Ops.end(),
+             [&](const ValPair &P1, const ValPair &P2) {
     return BlockInstRange.lookup(P1.second).first <
            BlockInstRange.lookup(P2.second).first;
   });
 }
 
 // Return true if V is a value that will always be available (IE can
 // be placed anywhere) in the function.  We don't do globals here
 // because they are often worse to put in place.
for (auto &B : RPOT) {
     auto *Node = DT->getNode(B);
     assert(Node && "RPO and Dominator tree should have same reachability");
     RPOOrdering[Node] = ++Counter;
   }
   // Sort dominator tree children arrays into RPO.
   for (auto &B : RPOT) {
     auto *Node = DT->getNode(B);
     if (Node->getChildren().size() > 1)
-      std::sort(Node->begin(), Node->end(),
+      llvm::sort(Node->begin(), Node->end(),
                  [&](const DomTreeNode *A, const DomTreeNode *B) {
                    return RPOOrdering[A] < RPOOrdering[B];
                  });
   }
 
   // Now a standard depth first ordering of the domtree is equivalent to RPO.
   for (auto DTN : depth_first(DT->getRootNode())) {
     BasicBlock *B = DTN->getBlock();
     const auto &BlockRange = assignDFSNumbers(B, ICount);
     BlockInstRange.insert({B, BlockRange});
     ICount += BlockRange.second - BlockRange.first;
if (alwaysAvailable(Leader)) {
         // the scope of those constants.
         ValueDFSStack EliminationStack;
 
         // Convert the members to DFS ordered sets and then merge them.
         SmallVector<ValueDFS, 8> DFSOrderedSet;
         convertClassToDFSOrdered(*CC, DFSOrderedSet, UseCounts, ProbablyDead);
 
         // Sort the whole thing.
-        std::sort(DFSOrderedSet.begin(), DFSOrderedSet.end());
+        llvm::sort(DFSOrderedSet.begin(), DFSOrderedSet.end());
         for (auto &VD : DFSOrderedSet) {
           int MemberDFSIn = VD.DFSIn;
           int MemberDFSOut = VD.DFSOut;
           Value *Def = VD.Def.getPointer();
           bool FromStore = VD.Def.getInt();
           Use *U = VD.U;
           // We ignore void things because we can't get a value from them.
           if (Def && Def->getType()->isVoidTy())
for (auto *Member : *CC)
       if (!isa<Instruction>(Member) ||
           !InstructionsToErase.count(cast<Instruction>(Member)))
         MembersLeft.insert(Member);
     CC->swap(MembersLeft);
 
     // If we have possible dead stores to look at, try to eliminate them.
     if (CC->getStoreCount() > 0) {
       convertClassToLoadsAndStores(*CC, PossibleDeadStores);
-      std::sort(PossibleDeadStores.begin(), PossibleDeadStores.end());
+      llvm::sort(PossibleDeadStores.begin(), PossibleDeadStores.end());
       ValueDFSStack EliminationStack;
       for (auto &VD : PossibleDeadStores) {
         int MemberDFSIn = VD.DFSIn;
         int MemberDFSOut = VD.DFSOut;
         Instruction *Member = cast<Instruction>(VD.Def.getPointer());
         if (EliminationStack.empty() ||
             !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
           // Sync to our current scope.

llvm/trunk/lib/Transforms/Scalar/PlaceSafepoints.cpp

if (enableBackedgeSafepoints(F)) {
 
     auto &PollLocations = PBS->PollLocations;
 
     auto OrderByBBName = [](Instruction *a, Instruction *b) {
       return a->getParent()->getName() < b->getParent()->getName();
     };
     // We need the order of list to be stable so that naming ends up stable
     // when we split edges.  This makes test cases much easier to write.
-    std::sort(PollLocations.begin(), PollLocations.end(), OrderByBBName);
+    llvm::sort(PollLocations.begin(), PollLocations.end(), OrderByBBName);
 
     // We can sometimes end up with duplicate poll locations.  This happens if
     // a single loop is visited more than once.   The fact this happens seems
     // wrong, but it does happen for the split-backedge.ll test case.
     PollLocations.erase(std::unique(PollLocations.begin(),
                                     PollLocations.end()),
                         PollLocations.end());
 

llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

for (User *U : Def->users()) {
         // ConstantExpr use itself or null.  In either case
         // (recursively in the first, directly in the second), the oop
         // it is ultimately dependent on is null and this particular
         // use does not need to be fixed up.
         Uses.push_back(cast<Instruction>(U));
       }
     }
 
-    std::sort(Uses.begin(), Uses.end());
+    llvm::sort(Uses.begin(), Uses.end());
     auto Last = std::unique(Uses.begin(), Uses.end());
     Uses.erase(Last, Uses.end());
 
     for (Instruction *Use : Uses) {
       if (isa<PHINode>(Use)) {
         PHINode *Phi = cast<PHINode>(Use);
         for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {
           if (Def == Phi->getIncomingValue(i)) {

llvm/trunk/lib/Transforms/Scalar/SROA.cpp

public:
   ///
   /// This moves the slices into the alloca's slices collection, and re-sorts
   /// everything so that the usual ordering properties of the alloca's slices
   /// hold.
   void insert(ArrayRef<Slice> NewSlices) {
     int OldSize = Slices.size();
     Slices.append(NewSlices.begin(), NewSlices.end());
     auto SliceI = Slices.begin() + OldSize;
-    std::sort(SliceI, Slices.end());
+    llvm::sort(SliceI, Slices.end());
     std::inplace_merge(Slices.begin(), SliceI, Slices.end());
   }
 
   // Forward declare the iterator and range accessor for walking the
   // partitions.
   class partition_iterator;
   iterator_range<partition_iterator> partitions();
 
if (SROARandomShuffleSlices) {
     std::mt19937 MT(static_cast<unsigned>(
         std::chrono::system_clock::now().time_since_epoch().count()));
     std::shuffle(Slices.begin(), Slices.end(), MT);
   }
 #endif
 
   // Sort the uses. This arranges for the offsets to be in ascending order,
   // and the sizes to be in descending order.
-  std::sort(Slices.begin(), Slices.end());
+  llvm::sort(Slices.begin(), Slices.end());
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 
 void AllocaSlices::print(raw_ostream &OS, const_iterator I,
                          StringRef Indent) const {
   printSlice(OS, I, Indent);
   OS << "\n";
auto RankVectorTypes = [&DL](VectorType *RHSTy, VectorType *LHSTy) {
       assert(DL.getTypeSizeInBits(RHSTy) == DL.getTypeSizeInBits(LHSTy) &&
              "Cannot have vector types of different sizes!");
       assert(RHSTy->getElementType()->isIntegerTy() &&
              "All non-integer types eliminated!");
       assert(LHSTy->getElementType()->isIntegerTy() &&
              "All non-integer types eliminated!");
       return RHSTy->getNumElements() < LHSTy->getNumElements();
     };
-    std::sort(CandidateTys.begin(), CandidateTys.end(), RankVectorTypes);
+    llvm::sort(CandidateTys.begin(), CandidateTys.end(), RankVectorTypes);
     CandidateTys.erase(
         std::unique(CandidateTys.begin(), CandidateTys.end(), RankVectorTypes),
         CandidateTys.end());
   } else {
 // The only way to have the same element type in every vector type is to
 // have the same vector type. Check that and remove all but one.
 #ifndef NDEBUG
     for (VectorType *VTy : CandidateTys) {
for (Slice &S : AS) {
           isa<StoreInst>(S.getUse()->getUser())) {
         S.makeUnsplittable();
         IsSorted = false;
       }
     }
   }
 
   if (!IsSorted)
-    std::sort(AS.begin(), AS.end());
+    llvm::sort(AS.begin(), AS.end());
 
   /// Describes the allocas introduced by rewritePartition in order to migrate
   /// the debug info.
   struct Fragment {
     AllocaInst *Alloca;
     uint64_t Offset;
     uint64_t Size;
     Fragment(AllocaInst *AI, uint64_t O, uint64_t S)

llvm/trunk/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

for (auto *ClonedBB : ClonedLoopBlocks)
     if (!BlocksInClonedLoop.count(ClonedBB))
       UnloopedBlockSet.insert(ClonedBB);
 
   // Copy the cloned exits and sort them in ascending loop depth, we'll work
   // backwards across these to process them inside out. The order shouldn't
   // matter as we're just trying to build up the map from inside-out; we use
   // the map in a more stably ordered way below.
   auto OrderedClonedExitsInLoops = ClonedExitsInLoops;
-  std::sort(OrderedClonedExitsInLoops.begin(), OrderedClonedExitsInLoops.end(),
+  llvm::sort(OrderedClonedExitsInLoops.begin(),
+             OrderedClonedExitsInLoops.end(),
              [&](BasicBlock *LHS, BasicBlock *RHS) {
                return ExitLoopMap.lookup(LHS)->getLoopDepth() <
                       ExitLoopMap.lookup(RHS)->getLoopDepth();
              });
 
   // Populate the existing ExitLoopMap with everything reachable from each
   // exit, starting from the inner most exit.
   while (!UnloopedBlockSet.empty() && !OrderedClonedExitsInLoops.empty()) {
     assert(Worklist.empty() && "Didn't clear worklist!");
 
     BasicBlock *ExitBB = OrderedClonedExitsInLoops.pop_back_val();
     Loop *ExitL = ExitLoopMap.lookup(ExitBB);

llvm/trunk/lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

Ostream << "-- Summary:\n"
                  InlinedNotImportedFunctionsToImportingModuleCount,
                  NotImportedFuncCount, "non-imported functions");
   Ostream.flush();
   dbgs() << Out;
 }
 
 void ImportedFunctionsInliningStatistics::calculateRealInlines() {
   // Removing duplicated Callers.
-  std::sort(NonImportedCallers.begin(), NonImportedCallers.end());
+  llvm::sort(NonImportedCallers.begin(), NonImportedCallers.end());
   NonImportedCallers.erase(
       std::unique(NonImportedCallers.begin(), NonImportedCallers.end()),
       NonImportedCallers.end());
 
   for (const auto &Name : NonImportedCallers) {
     auto &Node = *NodesMap[Name];
     if (!Node.Visited)
       dfs(Node);

 
 ImportedFunctionsInliningStatistics::SortedNodesTy
 ImportedFunctionsInliningStatistics::getSortedNodes() {
   SortedNodesTy SortedNodes;
   SortedNodes.reserve(NodesMap.size());
   for (const NodesMapTy::value_type& Node : NodesMap)
     SortedNodes.push_back(&Node);
 
-  std::sort(
+  llvm::sort(
       SortedNodes.begin(), SortedNodes.end(),
       [&](const SortedNodesTy::value_type &Lhs,
           const SortedNodesTy::value_type &Rhs) {
         if (Lhs->second->NumberOfInlines != Rhs->second->NumberOfInlines)
           return Lhs->second->NumberOfInlines > Rhs->second->NumberOfInlines;
-        if (Lhs->second->NumberOfRealInlines != Rhs->second->NumberOfRealInlines)
+        if (Lhs->second->NumberOfRealInlines !=
+            Rhs->second->NumberOfRealInlines)
           return Lhs->second->NumberOfRealInlines >
                  Rhs->second->NumberOfRealInlines;
         return Lhs->first() < Rhs->first();
       });
   return SortedNodes;
 }

llvm/trunk/lib/Transforms/Utils/LowerSwitch.cpp

 unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
   unsigned numCmps = 0;
 
   // Start with "simple" cases
   for (auto Case : SI->cases())
     Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
                               Case.getCaseSuccessor()));
 
-  std::sort(Cases.begin(), Cases.end(), CaseCmp());
+  llvm::sort(Cases.begin(), Cases.end(), CaseCmp());
 
   // Merge case into clusters
   if (Cases.size() >= 2) {
     CaseItr I = Cases.begin();
     for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
       int64_t nextValue = J->Low->getSExtValue();
       int64_t currentValue = I->High->getSExtValue();
       BasicBlock* nextBB = J->BB;

llvm/trunk/lib/Transforms/Utils/PredicateInfo.cpp

 // TODO: Use this algorithm to perform fast single-variable renaming in
 // promotememtoreg and memoryssa.
 void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpSet) {
   // Sort OpsToRename since we are going to iterate it.
   SmallVector<Value *, 8> OpsToRename(OpSet.begin(), OpSet.end());
   auto Comparator = [&](const Value *A, const Value *B) {
     return valueComesBefore(OI, A, B);
   };
-  std::sort(OpsToRename.begin(), OpsToRename.end(), Comparator);
+  llvm::sort(OpsToRename.begin(), OpsToRename.end(), Comparator);
   ValueDFS_Compare Compare(OI);
   // Compute liveness, and rename in O(uses) per Op.
   for (auto *Op : OpsToRename) {
     unsigned Counter = 0;
     SmallVector<ValueDFS, 16> OrderedUses;
     const auto &ValueInfo = getValueInfo(Op);
     // Insert the possible copies into the def/use list.
     // They will become real copies if we find a real use for them, and never

llvm/trunk/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

static bool promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info,
   StoresByIndexTy StoresByIndex;
 
   for (User *U : AI->users())
     if (StoreInst *SI = dyn_cast<StoreInst>(U))
       StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
 
   // Sort the stores by their index, making it efficient to do a lookup with a
   // binary search.
-  std::sort(StoresByIndex.begin(), StoresByIndex.end(), less_first());
+  llvm::sort(StoresByIndex.begin(), StoresByIndex.end(), less_first());
 
   // Walk all of the loads from this alloca, replacing them with the nearest
   // store above them, if any.
   for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
     LoadInst *LI = dyn_cast<LoadInst>(*UI++);
     if (!LI)
       continue;
 
for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
     // the standard SSA construction algorithm.  Determine which blocks need phi
     // nodes and see if we can optimize out some work by avoiding insertion of
     // dead phi nodes.
     IDF.setLiveInBlocks(LiveInBlocks);
     IDF.setDefiningBlocks(DefBlocks);
     SmallVector<BasicBlock *, 32> PHIBlocks;
     IDF.calculate(PHIBlocks);
     if (PHIBlocks.size() > 1)
-      std::sort(PHIBlocks.begin(), PHIBlocks.end(),
+      llvm::sort(PHIBlocks.begin(), PHIBlocks.end(),
                  [this](BasicBlock *A, BasicBlock *B) {
                    return BBNumbers.lookup(A) < BBNumbers.lookup(B);
                  });
 
     unsigned CurrentVersion = 0;
     for (BasicBlock *BB : PHIBlocks)
       QueuePhiNode(BB, AllocaNum, CurrentVersion);
   }
 
   if (Allocas.empty())
     return; // All of the allocas must have been trivial!
if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
       continue;
 
     // Get the preds for BB.
     SmallVector<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
 
     // Ok, now we know that all of the PHI nodes are missing entries for some
     // basic blocks.  Start by sorting the incoming predecessors for efficient
     // access.
-    std::sort(Preds.begin(), Preds.end());
+    llvm::sort(Preds.begin(), Preds.end());
 
     // Now we loop through all BB's which have entries in SomePHI and remove
     // them from the Preds list.
     for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
       // Do a log(n) search of the Preds list for the entry we want.
       SmallVectorImpl<BasicBlock *>::iterator EntIt = std::lower_bound(
           Preds.begin(), Preds.end(), SomePHI->getIncomingBlock(i));
       assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) &&

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder,
 
   // This transform is agnostic to the signedness of the input or case values. We
   // can treat the case values as signed or unsigned. We can optimize more common
   // cases such as a sequence crossing zero {-4,0,4,8} if we interpret case values
   // as signed.
   SmallVector<int64_t,4> Values;
   for (auto &C : SI->cases())
     Values.push_back(C.getCaseValue()->getValue().getSExtValue());
-  std::sort(Values.begin(), Values.end());
+  llvm::sort(Values.begin(), Values.end());
 
   // If the switch is already dense, there's nothing useful to do here.
   if (isSwitchDense(Values))
     return false;
 
   // First, transform the values such that they start at zero and ascend.
   int64_t Base = Values[0];
   for (auto &V : Values)

llvm/trunk/lib/Transforms/Utils/SplitModule.cpp

static void findPartitions(Module *M, ClusterIDMapType &ClusterIDMap,
   // When size is the same, use leader's name.
   for (ClusterMapType::iterator I = GVtoClusterMap.begin(),
                                 E = GVtoClusterMap.end(); I != E; ++I)
     if (I->isLeader())
       Sets.push_back(
           std::make_pair(std::distance(GVtoClusterMap.member_begin(I),
                                        GVtoClusterMap.member_end()), I));
 
-  std::sort(Sets.begin(), Sets.end(), [](const SortType &a, const SortType &b) {
+  llvm::sort(Sets.begin(), Sets.end(),
+             [](const SortType &a, const SortType &b) {
                if (a.first == b.first)
-      return a.second->getData()->getName() > b.second->getData()->getName();
+                 return a.second->getData()->getName() >
+                        b.second->getData()->getName();
                else
                  return a.first > b.first;
              });
 
   for (auto &I : Sets) {
     unsigned CurrentClusterID = BalancinQueue.top().first;
     unsigned CurrentClusterSize = BalancinQueue.top().second;
     BalancinQueue.pop();
 
     DEBUG(dbgs() << "Root[" << CurrentClusterID << "] cluster_size(" << I.first
                  << ") ----> " << I.second->getData()->getName() << "\n");