standardize {pred,succ,use,user}_{size,empty} like in MBB

[artagnon]

Summary

MachineBasicBlock has {pred,succ}_{size,empty}, and it would be nice to
have a version that operated on BasicBlock. While at it, add
implementations for use_, user_.

[sanjoy]

I'm not sure how much utility this adds -- what is a situation where you could profitably use these?

[artagnon]

In D6944#107856, @sanjoy wrote:

I'm not sure how much utility this adds -- what is a situation where you could profitably use these?

I designed this specifically for http://reviews.llvm.org/D6830 -- I imagine there must be many other instances?

[sanjoy]

In D6944#107857, @artagnon wrote:

In D6944#107856, @sanjoy wrote:

I'm not sure how much utility this adds -- what is a situation where you could profitably use these?

I designed this specifically for http://reviews.llvm.org/D6830 -- I imagine there must be many other instances?

I don't understand -- how would you use these in D6830?

[sanjoy]

I imagine there must be many other instances?

The case for this patch would be much stronger if you find a few of those instances and refactor them to use these *_size functions.

[ab]

include/llvm/IR/CFG.h

103

This is needlessly expensive when there are preds. How about checking for _end directly? (same for succ)

include/llvm/IR/Value.h

290

Nit: range-based for? (user_size as well)

[artagnon]

include/llvm/IR/CFG.h

103

Agreed; thanks.

include/llvm/IR/Value.h

290

I'm dropping .size() actually: you'll see why in the next iteration.

[artagnon]

Drop .size() functions, because they don't make any sense; it's
cheaper to do std::distance(.begin(), .end()). Put in a bunch of
usecases to support the .empty().

[atrick]

This latest version LGTM.

include/llvm/IR/CFG.h

 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
 inline const_pred_iterator pred_begin(const BasicBlock *BB) {
   return const_pred_iterator(BB);
 }
 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
 inline const_pred_iterator pred_end(const BasicBlock *BB) {
   return const_pred_iterator(BB, true);
 }
+inline bool pred_empty(const BasicBlock *BB) {
+  return pred_begin(BB) == pred_end(BB);
+}
 
 
 
 //===----------------------------------------------------------------------===//
 // BasicBlock succ_iterator definition
 //===----------------------------------------------------------------------===//
 
 template <class Term_, class BB_>           // Successor Iterator
 class SuccIterator : public std::iterator<std::random_access_iterator_tag, BB_,
                                           int, BB_ *, BB_ *> {
   typedef std::iterator<std::random_access_iterator_tag, BB_, int, BB_ *, BB_ *>
   super;
 
inline succ_const_iterator succ_begin(const BasicBlock *BB) {
   return succ_const_iterator(BB->getTerminator());
 }
 inline succ_iterator succ_end(BasicBlock *BB) {
   return succ_iterator(BB->getTerminator(), true);
 }
 inline succ_const_iterator succ_end(const BasicBlock *BB) {
   return succ_const_iterator(BB->getTerminator(), true);
 }
+inline bool succ_empty(const BasicBlock *BB) {
+  return succ_begin(BB) == succ_end(BB);
+}
 
 template <typename T, typename U> struct isPodLike<SuccIterator<T, U> > {
   static const bool value = isPodLike<T>::value;
 };
 
 
 
 //===--------------------------------------------------------------------===//

include/llvm/IR/Value.h

public:
   const_use_iterator use_end()   const { return const_use_iterator();   }
   iterator_range<use_iterator> uses() {
     return iterator_range<use_iterator>(use_begin(), use_end());
   }
   iterator_range<const_use_iterator> uses() const {
     return iterator_range<const_use_iterator>(use_begin(), use_end());
   }
 
+  bool               user_empty() const { return UseList == nullptr; }
+
   typedef user_iterator_impl<User>       user_iterator;
   typedef user_iterator_impl<const User> const_user_iterator;
   user_iterator       user_begin()       { return user_iterator(UseList); }
   const_user_iterator user_begin() const { return const_user_iterator(UseList); }
   user_iterator       user_end()         { return user_iterator();   }
   const_user_iterator user_end()   const { return const_user_iterator();   }
   User               *user_back()        { return *user_begin(); }
   const User         *user_back()  const { return *user_begin(); }

lib/Analysis/CFG.cpp

 /// FindFunctionBackedges - Analyze the specified function to find all of the
 /// loop backedges in the function and return them.  This is a relatively cheap
 /// (compared to computing dominators and loop info) analysis.
 ///
 /// The output is added to Result, as pairs of <from,to> edge info.
 void llvm::FindFunctionBackedges(const Function &F,
      SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
   const BasicBlock *BB = &F.getEntryBlock();
-  if (succ_begin(BB) == succ_end(BB))
+  if (succ_empty(BB))
     return;
 
   SmallPtrSet<const BasicBlock*, 8> Visited;
   SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
   SmallPtrSet<const BasicBlock*, 8> InStack;
 
   Visited.insert(BB);
   VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));

lib/IR/Verifier.cpp

Assert1(F.hasExternalLinkage() || F.hasExternalWeakLinkage(),
             "invalid linkage type for function declaration", &F);
   } else {
     // Verify that this function (which has a body) is not named "llvm.*".  It
     // is not legal to define intrinsics.
     Assert1(!isLLVMdotName, "llvm intrinsics cannot be defined!", &F);
 
     // Check the entry node
     const BasicBlock *Entry = &F.getEntryBlock();
-    Assert1(pred_begin(Entry) == pred_end(Entry),
+    Assert1(pred_empty(Entry),
             "Entry block to function must not have predecessors!", Entry);
 
     // The address of the entry block cannot be taken, unless it is dead.
     if (Entry->hasAddressTaken()) {
       Assert1(!BlockAddress::lookup(Entry)->isConstantUsed(),
               "blockaddress may not be used with the entry block!", Entry);
     }
   }

lib/Transforms/IPO/PruneEH.cpp

if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
         // Insert a branch to the normal destination right before the
         // invoke.
         BranchInst::Create(II->getNormalDest(), II);
 
         // Finally, delete the invoke instruction!
         BB->getInstList().pop_back();
 
         // If the unwind block is now dead, nuke it.
-        if (pred_begin(UnwindBlock) == pred_end(UnwindBlock))
+        if (pred_empty(UnwindBlock))
           DeleteBasicBlock(UnwindBlock);  // Delete the new BB.
 
         ++NumRemoved;
         MadeChange = true;
       }
 
     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
       if (CallInst *CI = dyn_cast<CallInst>(I++))
bool PruneEH::SimplifyFunction(Function *F) {
 
   return MadeChange;
 }
 
 /// DeleteBasicBlock - remove the specified basic block from the program,
 /// updating the callgraph to reflect any now-obsolete edges due to calls that
 /// exist in the BB.
 void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
-  assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
+  assert(pred_empty(BB) && "BB is not dead!");
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
 
   CallGraphNode *CGN = CG[BB->getParent()];
   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
     --I;
     if (CallInst *CI = dyn_cast<CallInst>(I)) {
       if (!isa<IntrinsicInst>(I))
         CGN->removeCallEdgeFor(CI);

lib/Transforms/Scalar/JumpThreading.cpp

for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
       // Thread all of the branches we can over this block.
       while (ProcessBlock(BB))
         Changed = true;
 
       ++I;
 
       // If the block is trivially dead, zap it.  This eliminates the successor
       // edges which simplifies the CFG.
-      if (pred_begin(BB) == pred_end(BB) &&
+      if (pred_empty(BB) &&
           BB != &BB->getParent()->getEntryBlock()) {
         DEBUG(dbgs() << "  JT: Deleting dead block '" << BB->getName()
               << "' with terminator: " << *BB->getTerminator() << '\n');
         LoopHeaders.erase(BB);
         LVI->eraseBlock(BB);
         DeleteDeadBlock(BB);
         Changed = true;
         continue;
static bool hasAddressTakenAndUsed(BasicBlock *BB) {
   return !BA->use_empty();
 }
 
 /// ProcessBlock - If there are any predecessors whose control can be threaded
 /// through to a successor, transform them now.
 bool JumpThreading::ProcessBlock(BasicBlock *BB) {
   // If the block is trivially dead, just return and let the caller nuke it.
   // This simplifies other transformations.
-  if (pred_begin(BB) == pred_end(BB) &&
+  if (pred_empty(BB) &&
       BB != &BB->getParent()->getEntryBlock())
     return false;
 
   // If this block has a single predecessor, and if that pred has a single
   // successor, merge the blocks.  This encourages recursive jump threading
   // because now the condition in this block can be threaded through
   // predecessors of our predecessor block.
   if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {

lib/Transforms/Scalar/Reg2Mem.cpp

INITIALIZE_PASS_END(RegToMem, "reg2mem", "Demote all values to stack slots",
                 false, false)
 
 bool RegToMem::runOnFunction(Function &F) {
   if (F.isDeclaration())
     return false;
 
   // Insert all new allocas into entry block.
   BasicBlock *BBEntry = &F.getEntryBlock();
-  assert(pred_begin(BBEntry) == pred_end(BBEntry) &&
+  assert(pred_empty(BBEntry) &&
          "Entry block to function must not have predecessors!");
 
   // Find first non-alloca instruction and create insertion point. This is
   // safe if block is well-formed: it always have terminator, otherwise
   // we'll get and assertion.
   BasicBlock::iterator I = BBEntry->begin();
   while (isa<AllocaInst>(I)) ++I;
 

lib/Transforms/Utils/SimplifyCFG.cpp

if (!UncondBranchPreds.empty() && DupRet) {
     while (!UncondBranchPreds.empty()) {
       BasicBlock *Pred = UncondBranchPreds.pop_back_val();
       DEBUG(dbgs() << "FOLDING: " << *BB
             << "INTO UNCOND BRANCH PRED: " << *Pred);
       (void)FoldReturnIntoUncondBranch(RI, BB, Pred);
     }
 
     // If we eliminated all predecessors of the block, delete the block now.
-    if (pred_begin(BB) == pred_end(BB))
+    if (pred_empty(BB))
       // We know there are no successors, so just nuke the block.
       BB->eraseFromParent();
 
     return true;
   }
 
   // Check out all of the conditional branches going to this return
   // instruction.  If any of them just select between returns, change the
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
         II->replaceAllUsesWith(CI);
         delete II;
         Changed = true;
       }
     }
   }
 
   // If this block is now dead, remove it.
-  if (pred_begin(BB) == pred_end(BB) &&
+  if (pred_empty(BB) &&
       BB != &BB->getParent()->getEntryBlock()) {
     // We know there are no successors, so just nuke the block.
     BB->eraseFromParent();
     return true;
   }
 
   return Changed;
 }

 bool SimplifyCFGOpt::run(BasicBlock *BB) {
   bool Changed = false;
 
   assert(BB && BB->getParent() && "Block not embedded in function!");
   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 
   // Remove basic blocks that have no predecessors (except the entry block)...
   // or that just have themself as a predecessor.  These are unreachable.
-  if ((pred_begin(BB) == pred_end(BB) &&
+  if ((pred_emtpy(BB) &&
        BB != &BB->getParent()->getEntryBlock()) ||
       BB->getSinglePredecessor() == BB) {
     DEBUG(dbgs() << "Removing BB: \n" << *BB);
     DeleteDeadBlock(BB);
     return true;
   }
 
   // Check to see if we can constant propagate this terminator instruction