Index: llvm/include/llvm/ADT/STLExtras.h =================================================================== --- llvm/include/llvm/ADT/STLExtras.h +++ llvm/include/llvm/ADT/STLExtras.h @@ -1539,35 +1539,47 @@ /// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N) /// time. Not meant for use with random-access iterators. -template +/// Can optionally take a predicate to filter lazily some items. +template ()) &)> bool hasNItems( IterTy &&Begin, IterTy &&End, unsigned N, + Pred &&ShouldBeCounted = + [](const decltype(*std::declval()) &) { return true; }, typename std::enable_if< !std::is_same< typename std::iterator_traits::type>::iterator_category, std::random_access_iterator_tag>::value, void>::type * = nullptr) { - for (; N; --N, ++Begin) + for (; N; ++Begin) { if (Begin == End) return false; // Too few. + N -= ShouldBeCounted(*Begin); + } return Begin == End; } /// Return true if the sequence [Begin, End) has N or more items. Runs in O(N) /// time. Not meant for use with random-access iterators. -template +/// Can optionally take a predicate to filter lazily some items. +template ()) &)> bool hasNItemsOrMore( IterTy &&Begin, IterTy &&End, unsigned N, + Pred &&ShouldBeCounted = + [](const decltype(*std::declval()) &) { return true; }, typename std::enable_if< !std::is_same< typename std::iterator_traits::type>::iterator_category, std::random_access_iterator_tag>::value, void>::type * = nullptr) { - for (; N; --N, ++Begin) + for (; N; ++Begin) { if (Begin == End) return false; // Too few. + N -= ShouldBeCounted(*Begin); + } return true; } Index: llvm/include/llvm/IR/User.h =================================================================== --- llvm/include/llvm/IR/User.h +++ llvm/include/llvm/IR/User.h @@ -218,6 +218,11 @@ NumUserOperands = NumOps; } + /// A dropable user is a user for which uses can be dropped without affecting + /// correctness and should be dropped rather than preventing a transformation + /// from happening. + bool isDropable() const; + // --------------------------------------------------------------------------- // Operand Iterator interface... // Index: llvm/include/llvm/IR/Value.h =================================================================== --- llvm/include/llvm/IR/Value.h +++ llvm/include/llvm/IR/Value.h @@ -444,6 +444,34 @@ /// This is logically equivalent to getNumUses() >= N. bool hasNUsesOrMore(unsigned N) const; + /// Return true if there is exactly one user of this value that cannot be + /// dropped. + /// + /// This is specialized because it is a common request and does not require + /// traversing the whole use list. + Use *getSingleUndropableUse(); + + /// Return true if there this value. + /// + /// This is specialized because it is a common request and does not require + /// traversing the whole use list. + bool hasNUndropableUses(unsigned N) const; + + /// Return true if this value has N users or more. + /// + /// This is logically equivalent to getNumUses() >= N. + bool hasNUndropableUsesOrMore(unsigned N) const; + + /// Remove every uses that can safely be removed. + /// + /// This will remove for example uses in llvm.assume. + /// This should be used when performing want to perform a tranformation but + /// some Dropable uses pervent it. + /// This function optionally takes a filter to only remove some dropable + /// uses. + void dropDropableUses(llvm::function_ref ShouldDrop = + [](const Use *) { return true; }); + /// Check if this value is used in the specified basic block. bool isUsedInBasicBlock(const BasicBlock *BB) const; Index: llvm/lib/IR/User.cpp =================================================================== --- llvm/lib/IR/User.cpp +++ llvm/lib/IR/User.cpp @@ -9,6 +9,7 @@ #include "llvm/IR/User.h" #include "llvm/IR/Constant.h" #include "llvm/IR/GlobalValue.h" +#include "llvm/IR/IntrinsicInst.h" namespace llvm { class BasicBlock; @@ -105,6 +106,12 @@ reinterpret_cast(DI) - DI->SizeInBytes, DI->SizeInBytes); } +bool User::isDropable() const { + if (const auto *Intr = dyn_cast(this)) + return Intr->getIntrinsicID() == Intrinsic::assume; + return false; +} + //===----------------------------------------------------------------------===// // User operator new Implementations //===----------------------------------------------------------------------===// Index: llvm/lib/IR/Value.cpp =================================================================== --- llvm/lib/IR/Value.cpp +++ llvm/lib/IR/Value.cpp @@ -137,6 +137,51 @@ return hasNItemsOrMore(use_begin(), use_end(), N); } +static bool isDropableUser(const User *U) { return U->isDropable(); } + +Use *Value::getSingleUndropableUse() { + Use *Result = nullptr; + for (Use &U : uses()) { + if (!U.getUser()->isDropable()) { + if (Result) + return nullptr; + Result = &U; + } + } + return Result; +} + +bool Value::hasNUndropableUses(unsigned int N) const { + return hasNItems(user_begin(), user_end(), N, isDropableUser); +} + +bool Value::hasNUndropableUsesOrMore(unsigned int N) const { + return hasNItemsOrMore(user_begin(), user_end(), N, isDropableUser); +} + +void Value::dropDropableUses( + llvm::function_ref ShouldDrop) { + SmallVector ToBeEdited; + for (Use &U : uses()) + if (U.getUser()->isDropable() && ShouldDrop(&U)) + ToBeEdited.push_back(&U); + for (Use *U : ToBeEdited) { + Value *V = U->get(); + (void)V; + if (auto *Assume = dyn_cast(U->getUser())) { + assert(Assume->getIntrinsicID() == Intrinsic::assume); + unsigned OpNo = U->getOperandNo(); + if (OpNo == 0) + Assume->setOperand(0, ConstantInt::getTrue(Assume->getContext())); + else + Assume->setOperand(OpNo, nullptr); + } else + llvm_unreachable("add special handeling here"); + assert(V != U->get() && "the value should have been changed"); + U->removeFromList(); + } +} + bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { // This can be computed either by scanning the instructions in BB, or by // scanning the use list of this Value. Both lists can be very long, but