ADT/STLExtras: Introduce llvm::empty(); NFC

[MatzeB]

Summary

This is modeled after C++17 std::empty().

(I got talked into shaving this yak in D53885)

[dblaikie]

(maybe some unit tests?)

Also, what about having only a single implementation:

template <typename Range>
constexpr bool empty(const Range &r) {
  return adl_begin(r) == adl_end(r);
}

Not sure why the standard library doesn't do it this way, but there are probably good reasons... though maybe they don't apply to us/llvm?

[MatzeB]

In D53909#1281525, @dblaikie wrote:

(maybe some unit tests?)

Also, what about having only a single implementation:

template <typename Range>
constexpr bool empty(const Range &r) {
  return adl_begin(r) == adl_end(r);
}

Not sure why the standard library doesn't do it this way, but there are probably good reasons... though maybe they don't apply to us/llvm?

What if the container has an optimized empty() method that works faster than actually producing begin and end iterators?

[MatzeB]

• Add a simple unittest
• Go with the adl_begin() == adl_end() implementation for now. We can always switch to more fine grained overloading when we actually deem it necessary for performance. And after all we will probably just replace it with std::empty() anyway once we use C++17 in llvm.

[dblaikie]

Sure - let's go with your original solution (plus the test case) for forwards-compatibility with the standard.

[dblaikie]

(oh, if you are going to switch back to the original implementation - probably put "empty" for iterator_range in iterator_range, rather than as a non-member)

include/llvm/ADT/STLExtras.h

 }
 
 template <typename T>
 void adl_swap(T &&lhs, T &&rhs) noexcept(
     noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
   adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
 }
 
+/// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
+template <typename T>
+constexpr bool empty(const T &RangeOrContainer) {
+  return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
+}
+
 // mapped_iterator - This is a simple iterator adapter that causes a function to
 // be applied whenever operator* is invoked on the iterator.
 
 template <typename ItTy, typename FuncTy,
           typename FuncReturnTy =
             decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
 class mapped_iterator
     : public iterator_adaptor_base<

lib/Analysis/LazyCallGraph.cpp

auto MergeRange = updatePostorderSequenceForEdgeInsertion(
       ComputeTargetConnectedSet);
 
   // Run the user's callback on the merged SCCs before we actually merge them.
   if (MergeCB)
     MergeCB(makeArrayRef(MergeRange.begin(), MergeRange.end()));
 
   // If the merge range is empty, then adding the edge didn't actually form any
   // new cycles. We're done.
-  if (MergeRange.begin() == MergeRange.end()) {
+  if (empty(MergeRange)) {
     // Now that the SCC structure is finalized, flip the kind to call.
     SourceN->setEdgeKind(TargetN, Edge::Call);
     return false; // No new cycle.
   }
 
 #ifndef NDEBUG
   // Before merging, check that the RefSCC remains valid after all the
   // postorder updates.

lib/CodeGen/GlobalISel/InstructionSelector.cpp

 bool InstructionSelector::isObviouslySafeToFold(MachineInstr &MI,
                                                 MachineInstr &IntoMI) const {
   // Immediate neighbours are already folded.
   if (MI.getParent() == IntoMI.getParent() &&
       std::next(MI.getIterator()) == IntoMI.getIterator())
     return true;
 
   return !MI.mayLoadOrStore() && !MI.hasUnmodeledSideEffects() &&
-         MI.implicit_operands().begin() == MI.implicit_operands().end();
+         empty(MI.implicit_operands());
 }

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
   assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
   return Result;
 }
 
 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
     std::initializer_list<unsigned> Opcodes) {
   unsigned Representative = *Opcodes.begin();
 
-  assert(Opcodes.begin() != Opcodes.end() &&
-         Opcodes.begin() + 1 != Opcodes.end() &&
+  assert(!empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
          "Initializer list must have at least two opcodes");
 
   for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
     aliasActionDefinitions(Representative, *I);
 
   auto &Return = getActionDefinitionsBuilder(Representative);
   Return.setIsAliasedByAnother();
   return Return;

lib/CodeGen/GlobalISel/RegBankSelect.cpp

 bool RegBankSelect::repairReg(
     MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping,
     RegBankSelect::RepairingPlacement &RepairPt,
     const iterator_range<SmallVectorImpl<unsigned>::const_iterator> &NewVRegs) {
   if (ValMapping.NumBreakDowns != 1 && !TPC->isGlobalISelAbortEnabled())
     return false;
   assert(ValMapping.NumBreakDowns == 1 && "Not yet implemented");
   // An empty range of new register means no repairing.
-  assert(NewVRegs.begin() != NewVRegs.end() && "We should not have to repair");
+  assert(!empty(NewVRegs) && "We should not have to repair");
 
   // Assume we are repairing a use and thus, the original reg will be
   // the source of the repairing.
   unsigned Src = MO.getReg();
   unsigned Dst = *NewVRegs.begin();
 
   // If we repair a definition, swap the source and destination for
   // the repairing.

lib/CodeGen/GlobalISel/RegisterBankInfo.cpp

for (unsigned OpIdx = 0,
     assert(OpdMapper.getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns !=
                0 &&
            "Invalid mapping");
     assert(OpdMapper.getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns ==
                1 &&
            "This mapping is too complex for this function");
     iterator_range<SmallVectorImpl<unsigned>::const_iterator> NewRegs =
         OpdMapper.getVRegs(OpIdx);
-    if (NewRegs.begin() == NewRegs.end()) {
+    if (empty(NewRegs)) {
       LLVM_DEBUG(dbgs() << " has not been repaired, nothing to be done\n");
       continue;
     }
     unsigned OrigReg = MO.getReg();
     unsigned NewReg = *NewRegs.begin();
     LLVM_DEBUG(dbgs() << " changed, replace " << printReg(OrigReg, nullptr));
     MO.setReg(NewReg);
     LLVM_DEBUG(dbgs() << " with " << printReg(NewReg, nullptr));

lib/ExecutionEngine/Orc/ExecutionUtils.cpp

 
 iterator_range<CtorDtorIterator> getDestructors(const Module &M) {
   const GlobalVariable *DtorsList = M.getNamedGlobal("llvm.global_dtors");
   return make_range(CtorDtorIterator(DtorsList, false),
                     CtorDtorIterator(DtorsList, true));
 }
 
 void CtorDtorRunner::add(iterator_range<CtorDtorIterator> CtorDtors) {
-  if (CtorDtors.begin() == CtorDtors.end())
+  if (empty(CtorDtors))
     return;
 
   MangleAndInterner Mangle(
       JD.getExecutionSession(),
       (*CtorDtors.begin()).Func->getParent()->getDataLayout());
 
   for (const auto &CtorDtor : CtorDtors) {
     assert(CtorDtor.Func && CtorDtor.Func->hasName() &&

lib/IR/DebugInfo.cpp

if (Scope->getNumOperands() == 0)
     return false;
   if (!NodesSeen.insert(Scope).second)
     return false;
   Scopes.push_back(Scope);
   return true;
 }
 
 static MDNode *stripDebugLocFromLoopID(MDNode *N) {
-  assert(N->op_begin() != N->op_end() && "Missing self reference?");
+  assert(!empty(N->operands()) && "Missing self reference?");
 
   // if there is no debug location, we do not have to rewrite this MDNode.
   if (std::none_of(N->op_begin() + 1, N->op_end(), [](const MDOperand &Op) {
         return isa<DILocation>(Op.get());
       }))
     return N;
 
   // If there is only the debug location without any actual loop metadata, we

lib/Transforms/IPO/PartialInlining.cpp

if (F->hasFnAttribute(Attribute::AlwaysInline))
     return {false, nullptr};
 
   if (F->hasFnAttribute(Attribute::NoInline))
     return {false, nullptr};
 
   if (PSI->isFunctionEntryCold(F))
     return {false, nullptr};
 
-  if (F->user_begin() == F->user_end())
+  if (empty(F->users()))
     return {false, nullptr};
 
   OptimizationRemarkEmitter ORE(F);
 
   // Only try to outline cold regions if we have a profile summary, which
   // implies we have profiling information.
   if (PSI->hasProfileSummary() && F->hasProfileData() &&
       !DisableMultiRegionPartialInline) {
OrigFuncORE.emit([&]() {
              << " not partially inlined into callers (Original Size = "
              << ore::NV("OutlinedRegionOriginalSize", Cloner.OutlinedRegionCost)
              << ", Size of call sequence to outlined function = "
              << ore::NV("NewSize", SizeCost) << ")";
     });
     return false;
   }
 
-  assert(Cloner.OrigFunc->user_begin() == Cloner.OrigFunc->user_end() &&
+  assert(empty(Cloner.OrigFunc->users()) &&
          "F's users should all be replaced!");
 
   std::vector<User *> Users(Cloner.ClonedFunc->user_begin(),
                             Cloner.ClonedFunc->user_end());
 
   DenseMap<User *, uint64_t> CallSiteToProfCountMap;
   auto CalleeEntryCount = Cloner.OrigFunc->getEntryCount();
   if (CalleeEntryCount)

lib/Transforms/Scalar/NewGVN.cpp

NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,
   auto Filtered = make_filter_range(E->operands(), [&](Value *Arg) {
     if (isa<UndefValue>(Arg)) {
       HasUndef = true;
       return false;
     }
     return true;
   });
   // If we are left with no operands, it's dead.
-  if (Filtered.begin() == Filtered.end()) {
+  if (empty(Filtered)) {
     // If it has undef at this point, it means there are no-non-undef arguments,
     // and thus, the value of the phi node must be undef.
     if (HasUndef) {
       LLVM_DEBUG(
           dbgs() << "PHI Node " << *I
                  << " has no non-undef arguments, valuing it as undef\n");
       return createConstantExpression(UndefValue::get(I->getType()));
     }

lib/Transforms/Utils/PredicateInfo.cpp

for (auto RenameIter = RenameStack.end() - Start;
     // For edge predicates, we can just place the operand in the block before
     // the terminator.  For assume, we have to place it right before the assume
     // to ensure we dominate all of our uses.  Always insert right before the
     // relevant instruction (terminator, assume), so that we insert in proper
     // order in the case of multiple predicateinfo in the same block.
     if (isa<PredicateWithEdge>(ValInfo)) {
       IRBuilder<> B(getBranchTerminator(ValInfo));
       Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
-      if (IF->user_begin() == IF->user_end())
+      if (empty(IF->users()))
         CreatedDeclarations.insert(IF);
       CallInst *PIC =
           B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
       PredicateMap.insert({PIC, ValInfo});
       Result.Def = PIC;
     } else {
       auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
       assert(PAssume &&
              "Should not have gotten here without it being an assume");
       IRBuilder<> B(PAssume->AssumeInst);
       Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
-      if (IF->user_begin() == IF->user_end())
+      if (empty(IF->users()))
         CreatedDeclarations.insert(IF);
       CallInst *PIC = B.CreateCall(IF, Op);
       PredicateMap.insert({PIC, ValInfo});
       Result.Def = PIC;
     }
   }
   return RenameStack.back().Def;
 }

lib/Transforms/Utils/SimplifyCFG.cpp

static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
 
   // Ignore switches with less than three cases. Lookup tables will not make
   // them faster, so we don't analyze them.
   if (SI->getNumCases() < 3)
     return false;
 
   // Figure out the corresponding result for each case value and phi node in the
   // common destination, as well as the min and max case values.
-  assert(SI->case_begin() != SI->case_end());
+  assert(!empty(SI->cases()));
   SwitchInst::CaseIt CI = SI->case_begin();
   ConstantInt *MinCaseVal = CI->getCaseValue();
   ConstantInt *MaxCaseVal = CI->getCaseValue();
 
   BasicBlock *CommonDest = nullptr;
 
   using ResultListTy = SmallVector<std::pair<ConstantInt *, Constant *>, 4>;
   SmallDenseMap<PHINode *, ResultListTy> ResultLists;

unittests/ADT/STLExtrasTest.cpp

TEST(STLExtrasTest, ADLTest) {
   EXPECT_EQ(s.swap_val, "lhs");
   EXPECT_EQ(s2.swap_val, "rhs");
 
   int count = 0;
   llvm::for_each(s, [&count](int) { ++count; });
   EXPECT_EQ(5, count);
 }
 
+TEST(STLExtrasTest, EmptyTest) {
+  std::vector<void*> V;
+  EXPECT_TRUE(empty(V));
+  V.push_back(nullptr);
+  EXPECT_FALSE(empty(V));
+
+  std::initializer_list<int> E = {};
+  std::initializer_list<int> NotE = {7, 13, 42};
+  EXPECT_TRUE(empty(E));
+  EXPECT_FALSE(empty(NotE));
+
+  auto R0 = make_range(V.begin(), V.begin());
+  EXPECT_TRUE(empty(R0));
+  auto R1 = make_range(V.begin(), V.end());
+  EXPECT_FALSE(empty(R1));
+}
+
 TEST(STLExtrasTest, EarlyIncrementTest) {
   std::list<int> L = {1, 2, 3, 4};
 
   auto EIR = make_early_inc_range(L);
 
   auto I = EIR.begin();
   auto EI = EIR.end();
   EXPECT_NE(I, EI);