[BasicBlock] Add instructionsWithoutDebug methods to skip debug insts.

[mattd]

include/llvm/IR/BasicBlock.h

185

I realize \brief is used throughout this header, but I do not think that is necessary anymore, because the Doxygen.cfg has AutoBrief on.

include/llvm/IR/Instruction.h

703

I like how you made this a struct instead of just a variadic function. I was exploring a similar solution, as discussed in the aforementioned thread, but had ambiguity issues with the base case. Looks like you cracked that! I like this.

I wonder if it makes more sense to push this up into Casting.h since it's as specific as isa<>.

[aprantl]

include/llvm/IR/BasicBlock.h

185

Yes, please avoid \brief.
Bonus points for a separate NFC commit that removes \brief from the entire header :-)

[vsk]

I like the direction this is going in :).

I think having an API like 'instructions_no_debug' or similar in BasicBlock would make the interface friendlier. For one, it'd signal to readers that skipping debug intrinsics is an established pattern. Also, I think it would be easier to change if, e.g we wanted update all existing users of the API to skip lifetime intrinsics too.

lib/Transforms/IPO/PartialInlining.cpp

853

I think this changes the inline cost of debug info intrinsics from InstrCost to 0. That seems like a correct and worthwhile change, but would probably be best to tackle in a follow-up patch.

854

Fwiw, I found the switch a little easier to read. I'm not sure it's a clear readability improvement to put these type checks into template parameters.

[dblaikie]

In D45657#1068834, @vsk wrote:

I like the direction this is going in :).

I think having an API like 'instructions_no_debug' or similar in BasicBlock would make the interface friendlier. For one, it'd signal to readers that skipping debug intrinsics is an established pattern. Also, I think it would be easier to change if, e.g we wanted update all existing users of the API to skip lifetime intrinsics too.

+1

include/llvm/IR/BasicBlock.h

198

Indirection through a function pointer may not be optimized away - may be worth baking this into a functor type?

[mattd]

include/llvm/IR/BasicBlock.h

185

Bonus points for a separate NFC commit that removes \brief from the entire header :-)

Challenge accepted.

[fhahn]

In D45657#1068834, @vsk wrote:

I like the direction this is going in :).

I think having an API like 'instructions_no_debug' or similar in BasicBlock would make the interface friendlier. For one, it'd signal to readers that skipping debug intrinsics is an established pattern. Also, I think it would be easier to change if, e.g we wanted update all existing users of the API to skip lifetime intrinsics too.

Thanks for the feedback! I'll add a instructionsNoDebug function. I tried to make skipInsts as flexible as possible, but I am not sure if the flexibility is really needed. Should I remove it for now?

include/llvm/IR/BasicBlock.h

198

Will do

unittests/IR/BasicBlockTest.cpp

17

I'll remove this.

[vsk]

In D45657#1070122, @fhahn wrote:

In D45657#1068834, @vsk wrote:

I like the direction this is going in :).

I think having an API like 'instructions_no_debug' or similar in BasicBlock would make the interface friendlier. For one, it'd signal to readers that skipping debug intrinsics is an established pattern. Also, I think it would be easier to change if, e.g we wanted update all existing users of the API to skip lifetime intrinsics too.

Thanks for the feedback! I'll add a instructionsNoDebug function. I tried to make skipInsts as flexible as possible, but I am not sure if the flexibility is really needed. Should I remove it for now?

It should be possible to implement instructionsNoDebug succinctly without skipInsts, so I'd suggest removing it.

I think the is_{any,none}_of predicates could be generally useful, though. It'd make sense to add them as a follow-up.

[fhahn]

Simplified things, only add methods to skip debug instructions.

[fhahn]

The only problem with those functions is that we cannot reverse a filter_iterator at the moment, as needed for D45379. But I suppose that should be fixable too.

[mattd]

Thanks! This looks really nice.

[vsk]

Thanks, lgtm as well. I sent out a patch to fix the issue with reversing filtered iterator ranges (https://reviews.llvm.org/D45792).

include/llvm/IR/BasicBlock.h

public:
   ///
   /// In particular, it skips all PHIs and LandingPad instructions.
   const_iterator getFirstInsertionPt() const;
   iterator getFirstInsertionPt() {
     return static_cast<const BasicBlock *>(this)
                                           ->getFirstInsertionPt().getNonConst();
   }
 
+  /// \brief Return an iterator over the instructions in the block, skipping any
+  /// instances of any of the template arguments.
+  template <typename... Args>
+  iterator_range<filter_iterator<BasicBlock::const_iterator,
+                                 bool (*)(const Instruction &)>>
+  skipInsts() const {
+    return make_filter_range(*this, is_none_of<Args...>);
+  }
+
+  /// \brief Return an iterator over the instructions in the block, skipping any
+  /// instances of any of the template arguments.
+  template <typename... Args>
+  iterator_range<
+      filter_iterator<BasicBlock::iterator, bool (*)(const Instruction &)>>
+  skipInsts() {
+    return make_filter_range(*this, is_none_of<Args...>);
+  }
+
   /// \brief Unlink 'this' from the containing function, but do not delete it.
   void removeFromParent();
 
   /// \brief Unlink 'this' from the containing function and delete it.
   ///
   // \returns an iterator pointing to the element after the erased one.
   SymbolTableList<BasicBlock>::iterator eraseFromParent();
 

include/llvm/IR/Instruction.h

private:
   /// Create a copy of this instruction.
   Instruction *cloneImpl() const;
 };
 
 inline void ilist_alloc_traits<Instruction>::deleteNode(Instruction *V) {
   V->deleteValue();
 }
 
+namespace detail {
+template <typename... Ts> struct is_any_of_impl;
+
+template <typename T, typename... Ts> struct is_any_of_impl<T, Ts...> {
+  static bool impl(const Instruction &I) {
+    return isa<T>(I) || is_any_of_impl<Ts...>::impl(I);
+  }
+};
+
+template <> struct is_any_of_impl<> {
+  static bool impl(const Instruction &I) { return false; }
+};
+} // namespace detail
+
+/// Return true if I is an instance of any of the template type arguments.
+template <typename... Ts> bool is_any_of(const Instruction &I) {
+  return detail::is_any_of_impl<Ts...>::impl(I);
+}
+
+/// Return true if I is an instance of none of the template type arguments.
+template <typename... Ts> bool is_none_of(const Instruction &I) {
+  return !detail::is_any_of_impl<Ts...>::impl(I);
+}
+
 } // end namespace llvm
 
 #endif // LLVM_IR_INSTRUCTION_H

lib/Transforms/IPO/GlobalOpt.cpp

static bool cxxDtorIsEmpty(const Function &Fn,
   // nounwind, but that doesn't seem worth doing.
   if (Fn.isDeclaration())
     return false;
 
   if (++Fn.begin() != Fn.end())
     return false;
 
   const BasicBlock &EntryBlock = Fn.getEntryBlock();
-  for (BasicBlock::const_iterator I = EntryBlock.begin(), E = EntryBlock.end();
-       I != E; ++I) {
-    if (const CallInst *CI = dyn_cast<CallInst>(I)) {
-      // Ignore debug intrinsics.
-      if (isa<DbgInfoIntrinsic>(CI))
-        continue;
-
+  for (const Instruction &I : EntryBlock.skipInsts<DbgInfoIntrinsic>()) {
+    if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
       const Function *CalledFn = CI->getCalledFunction();
 
       if (!CalledFn)
         return false;
 
       SmallPtrSet<const Function *, 8> NewCalledFunctions(CalledFunctions);
 
       // Don't treat recursive functions as empty.
       if (!NewCalledFunctions.insert(CalledFn).second)
         return false;
 
       if (!cxxDtorIsEmpty(*CalledFn, NewCalledFunctions))
         return false;
-    } else if (isa<ReturnInst>(*I))
+    } else if (isa<ReturnInst>(I))
       return true; // We're done.
-    else if (I->mayHaveSideEffects())
+    else if (I.mayHaveSideEffects())
       return false; // Destructor with side effects, bail.
   }
 
   return false;
 }
 
 static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
   /// Itanium C++ ABI p3.3.5:

lib/Transforms/IPO/PartialInlining.cpp

 }
 
 // TODO: Ideally  we should share Inliner's InlineCost Analysis code.
 // For now use a simplified version. The returned 'InlineCost' will be used
 // to esimate the size cost as well as runtime cost of the BB.
 int PartialInlinerImpl::computeBBInlineCost(BasicBlock *BB) {
   int InlineCost = 0;
   const DataLayout &DL = BB->getParent()->getParent()->getDataLayout();
-  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
-    if (isa<DbgInfoIntrinsic>(I))
+  for (Instruction &I : BB->skipInsts<AllocaInst, BitCastInst, DbgInfoIntrinsic,
+                                      IntToPtrInst, PtrToIntInst>()) {
+    if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I))
+      if (GEP->hasAllZeroIndices())
         continue;
 
-    switch (I->getOpcode()) {
-    case Instruction::BitCast:
-    case Instruction::PtrToInt:
-    case Instruction::IntToPtr:
-    case Instruction::Alloca:
-      continue;
-    case Instruction::GetElementPtr:
-      if (cast<GetElementPtrInst>(I)->hasAllZeroIndices())
-        continue;
-      break;
-    default:
-      break;
-    }
-
-    IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(I);
+    IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&I);
     if (IntrInst) {
       if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start ||
           IntrInst->getIntrinsicID() == Intrinsic::lifetime_end)
         continue;
     }
 
-    if (CallInst *CI = dyn_cast<CallInst>(I)) {
+    if (CallInst *CI = dyn_cast<CallInst>(&I)) {
       InlineCost += getCallsiteCost(CallSite(CI), DL);
       continue;
     }
 
-    if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
+    if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
       InlineCost += getCallsiteCost(CallSite(II), DL);
       continue;
     }
 
-    if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
+    if (SwitchInst *SI = dyn_cast<SwitchInst>(&I)) {
       InlineCost += (SI->getNumCases() + 1) * InlineConstants::InstrCost;
       continue;
     }
     InlineCost += InlineConstants::InstrCost;
   }
   return InlineCost;
 }
 

lib/Transforms/Scalar/GVN.cpp

for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {
     // Nothing to PRE in the entry block.
     if (CurrentBlock == &F.getEntryBlock())
       continue;
 
     // Don't perform PRE on an EH pad.
     if (CurrentBlock->isEHPad())
       continue;
 
-    for (BasicBlock::iterator BI = CurrentBlock->begin(),
-                              BE = CurrentBlock->end();
-         BI != BE;) {
+    auto InstRange = CurrentBlock->skipInsts<DbgInfoIntrinsic>();
+    for (auto BI = InstRange.begin(), BE = InstRange.end(); BI != BE;) {
       Instruction *CurInst = &*BI++;
       Changed |= performScalarPRE(CurInst);
     }
   }
 
   if (splitCriticalEdges())
     Changed = true;
 

lib/Transforms/Utils/LoopSimplify.cpp

for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
       if (!BI || !BI->isConditional()) continue;
       CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
       if (!CI || CI->getParent() != ExitingBlock) continue;
 
       // Attempt to hoist out all instructions except for the
       // comparison and the branch.
       bool AllInvariant = true;
       bool AnyInvariant = false;
-      for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) {
+      for (auto I = ExitingBlock->skipInsts<DbgInfoIntrinsic>().begin();
+           &*I != BI;) {
         Instruction *Inst = &*I++;
-        // Skip debug info intrinsics.
-        if (isa<DbgInfoIntrinsic>(Inst))
-          continue;
         if (Inst == CI)
           continue;
         if (!L->makeLoopInvariant(Inst, AnyInvariant,
                                   Preheader ? Preheader->getTerminator()
                                             : nullptr)) {
           AllInvariant = false;
           break;
         }

lib/Transforms/Utils/LoopUnroll.cpp

LoopUnrollResult llvm::UnrollLoop(
   // share the same exit blocks). We'll keep track of loops for which we can
   // break this so that later we can re-simplify them.
   SmallSetVector<Loop *, 4> LoopsToSimplify;
   for (Loop *SubLoop : *L)
     LoopsToSimplify.insert(SubLoop);
 
   if (Header->getParent()->isDebugInfoForProfiling())
     for (BasicBlock *BB : L->getBlocks())
-      for (Instruction &I : *BB)
-        if (!isa<DbgInfoIntrinsic>(&I))
-          if (const DILocation *DIL = I.getDebugLoc())
-            I.setDebugLoc(DIL->cloneWithDuplicationFactor(Count));
+      for (Instruction &I : BB->skipInsts<DbgInfoIntrinsic>())
 
   for (unsigned It = 1; It != Count; ++It) {
     std::vector<BasicBlock*> NewBlocks;
     SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
     NewLoops[L] = L;
 
     for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
       ValueToValueMapTy VMap;

unittests/IR/BasicBlockTest.cpp

 //===- llvm/unittest/IR/BasicBlockTest.cpp - BasicBlock unit tests --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/NoFolder.h"
+#include "llvm/Support/Debug.h"
 #include "gmock/gmock-matchers.h"
 #include "gtest/gtest.h"
 #include <memory>
 
 namespace llvm {
 namespace {
 
 TEST(BasicBlockTest, PhiRange) {
TEST(BasicBlockTest, PhiRange) {
   // And iterate a const range.
   for (const auto &PN : const_cast<const BasicBlock *>(BB.get())->phis()) {
     EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));
     EXPECT_EQ(BB1.get(), PN.getIncomingBlock(1));
     EXPECT_EQ(BB2.get(), PN.getIncomingBlock(2));
   }
 }
 
+#define CHECK_ITERATORS(Range1, Range2)                                        \
+  EXPECT_EQ(std::distance(Range1.begin(), Range1.end()),                       \
+            std::distance(Range2.begin(), Range2.end()));                      \
+  for (auto Pair : zip(Range1, Range2))                                        \
+    EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));
+
+TEST(BasicBlockTest, TestSkipInsts) {
+  LLVMContext Ctx;
+
+  std::unique_ptr<Module> M(new Module("MyModule", Ctx));
+  Type *ArgTy1[] = {Type::getInt32PtrTy(Ctx)};
+  FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), ArgTy1, false);
+  auto *V = new Argument(Type::getInt32Ty(Ctx));
+  Function *F = Function::Create(FT, Function::ExternalLinkage, "", M.get());
+
+  BasicBlock *BB1 = BasicBlock::Create(Ctx, "", F);
+  const BasicBlock *BBConst = BB1;
+  IRBuilder<> Builder1(BB1);
+
+  AllocaInst *Var = Builder1.CreateAlloca(Builder1.getInt8Ty());
+  CallInst *Start = Builder1.CreateLifetimeStart(Var);
+  Instruction *AddInst = cast<Instruction>(Builder1.CreateAdd(V, V));
+  Instruction *MulInst = cast<Instruction>(Builder1.CreateMul(AddInst, V));
+  Instruction *SubInst = cast<Instruction>(Builder1.CreateSub(MulInst, V));
+
+  SmallVector<Instruction *, 4> Exp = {Var, Start};
+  CHECK_ITERATORS(BB1->skipInsts<BinaryOperator>(), Exp);
+  CHECK_ITERATORS(BBConst->skipInsts<BinaryOperator>(), Exp);
+
+  SmallVector<Instruction *, 1> Exp2 = {Var};
+  auto SkippedIter1 = BB1->skipInsts<BinaryOperator, CallInst>();
+  CHECK_ITERATORS(SkippedIter1, Exp2);
+
+  auto SkippedIter2 = BBConst->skipInsts<BinaryOperator, CallInst>();
+  CHECK_ITERATORS(SkippedIter2, Exp2);
+
+  SmallVector<Instruction *, 1> Exp3 = {};
+  auto SkippedIter3 = BB1->skipInsts<BinaryOperator, CallInst, AllocaInst>();
+  CHECK_ITERATORS(SkippedIter3, Exp3);
+
+  auto SkippedIter4 =
+      BBConst->skipInsts<BinaryOperator, CallInst, AllocaInst>();
+  CHECK_ITERATORS(SkippedIter4, Exp3);
+
+  SmallVector<Instruction *, 4> Exp4 = {Var, AddInst, MulInst, SubInst};
+  CHECK_ITERATORS(BB1->skipInsts<CallInst>(), Exp4);
+  CHECK_ITERATORS(BBConst->skipInsts<CallInst>(), Exp4);
+}
+
 } // End anonymous namespace.
 } // End llvm namespace.

unittests/IR/InstructionsTest.cpp

 }
 
 TEST(InstructionsTest, CommuteShuffleMask) {
   SmallVector<int, 16> Indices({-1, 0, 7});
   ShuffleVectorInst::commuteShuffleMask(Indices, 4);
   EXPECT_THAT(Indices, testing::ContainerEq(ArrayRef<int>({-1, 4, 3})));
 }
 
+TEST_F(ModuleWithFunctionTest, IsAnyOfAndIsNoneOf) {
+  auto *OnlyBB = BasicBlock::Create(Ctx, "bb", F);
+  auto *Arg0 = &*F->arg_begin();
+
+  IRBuilder<NoFolder> B(OnlyBB);
+  AllocaInst &Var = *B.CreateAlloca(B.getInt8Ty());
+  bool Any1 = is_any_of<LoadInst, AllocaInst, CallInst>(Var);
+  bool Any2 = is_any_of<LoadInst, StoreInst, CallInst>(Var);
+  EXPECT_TRUE(Any1);
+  EXPECT_FALSE(Any2);
+
+  bool None1 = is_none_of<LoadInst, AllocaInst, CallInst>(Var);
+  bool None2 = is_none_of<LoadInst, StoreInst, CallInst>(Var);
+  EXPECT_FALSE(None1);
+  EXPECT_TRUE(None2);
+
+  Instruction &Start = *B.CreateLifetimeStart(&Var);
+  bool Any3 = is_any_of<LoadInst, AllocaInst, CallInst>(Start);
+  bool Any4 = is_any_of<LoadInst, StoreInst, AllocaInst, BinaryOperator>(Start);
+  EXPECT_TRUE(Any3);
+  EXPECT_FALSE(Any4);
+
+  bool None3 = is_none_of<LoadInst, AllocaInst, CallInst>(Start);
+  bool None4 =
+      is_none_of<LoadInst, StoreInst, AllocaInst, BinaryOperator>(Start);
+  EXPECT_FALSE(None3);
+  EXPECT_TRUE(None4);
+
+  Instruction &AddInst = *cast<Instruction>(B.CreateAdd(Arg0, Arg0));
+  bool Any5 =
+      is_any_of<LoadInst, StoreInst, AllocaInst, BinaryOperator>(AddInst);
+  bool Any6 = is_any_of<LoadInst, AllocaInst, CallInst>(AddInst);
+  EXPECT_TRUE(Any5);
+  EXPECT_FALSE(Any6);
+
+  bool None5 =
+      is_any_of<LoadInst, StoreInst, AllocaInst, BinaryOperator>(AddInst);
+  bool None6 = is_any_of<LoadInst, AllocaInst, CallInst>(AddInst);
+  EXPECT_TRUE(None5);
+  EXPECT_FALSE(None6);
+}
+
 } // end anonymous namespace
 } // end namespace llvm