diff --git a/llvm/include/llvm/IR/Use.h b/llvm/include/llvm/IR/Use.h --- a/llvm/include/llvm/IR/Use.h +++ b/llvm/include/llvm/IR/Use.h @@ -85,7 +85,7 @@ return (Use **)P; } - static constexpr int NumLowBitsAvailable = 2; + static constexpr int NumLowBitsAvailable = 3; }; private: @@ -100,8 +100,23 @@ /// Constructor Use(PrevPtrTag tag) { Prev.setInt(tag); } + static constexpr unsigned isDroppableMask = 1 << 2; + +#ifndef NDEBUG + bool checkDroppable() const; +#endif + void setDroppable() { + Prev.setInt(Prev.getInt() | isDroppableMask); + } + public: friend class Value; + friend class User; + + bool isDroppable() const { + assert(checkDroppable() && "the use should be marked droppable"); + return Prev.getInt() & isDroppableMask; + } operator Value *() const { return Val; } Value *get() const { return Val; } @@ -139,10 +154,21 @@ const Use *getImpliedUser() const LLVM_READONLY; Value *Val = nullptr; - Use *Next = nullptr; - PointerIntPair Prev; + /// This is aligned on 8 so that it allways have the 3 bottom bits + /// available. + alignas(8) Use *Next = nullptr; + + /// The pointer point to the Use::Next of the previous node or the + /// Value::UseList of the associated value. *Prev.getPointer() is always the + /// a pointer to the use itself. + /// In the Int the 2 lowest bits are the Tag used for waymarking. + /// The third lowest bit is wether the use is droppable or not. + PointerIntPair Prev; void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); } + PrevPtrTag getTag() const LLVM_READONLY { + return static_cast(Prev.getInt() & ~isDroppableMask); + } void addToList(Use **List) { Next = *List; diff --git a/llvm/include/llvm/IR/User.h b/llvm/include/llvm/IR/User.h --- a/llvm/include/llvm/IR/User.h +++ b/llvm/include/llvm/IR/User.h @@ -223,6 +223,10 @@ /// from happening. bool isDroppable() const; + /// This will mark every use as droppable if the user is droppable. + /// This should be called from + void maybeMarkUsesAsDroppable(); + // --------------------------------------------------------------------------- // Operand Iterator interface... // diff --git a/llvm/include/llvm/IR/Value.h b/llvm/include/llvm/IR/Value.h --- a/llvm/include/llvm/IR/Value.h +++ b/llvm/include/llvm/IR/Value.h @@ -75,7 +75,9 @@ // The least-significant bit of the first word of Value *must* be zero: // http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm Type *VTy; - Use *UseList; + /// This is aligned on 8 so that it allways have the 3 bottom bits + /// available. + alignas(8) Use *UseList; friend class ValueAsMetadata; // Allow access to IsUsedByMD. friend class ValueHandleBase; @@ -449,7 +451,17 @@ /// /// This is specialized because it is a common request and does not require /// traversing the whole use list. - Use *getSingleUndroppableUse(); + Use *getSingleUndroppableUse() { + Use *Result = nullptr; + for (Use &U : uses()) { + if (!U.isDroppable()) { + if (Result) + return nullptr; + Result = &U; + } + } + return Result; + } /// Return true if there this value. /// diff --git a/llvm/lib/IR/Instructions.cpp b/llvm/lib/IR/Instructions.cpp --- a/llvm/lib/IR/Instructions.cpp +++ b/llvm/lib/IR/Instructions.cpp @@ -460,6 +460,7 @@ assert(It + 1 == op_end() && "Should add up!"); setName(NameStr); + maybeMarkUsesAsDroppable(); } void CallInst::init(FunctionType *FTy, Value *Func, const Twine &NameStr) { @@ -470,6 +471,7 @@ assert(FTy->getNumParams() == 0 && "Calling a function with bad signature"); setName(NameStr); + maybeMarkUsesAsDroppable(); } CallInst::CallInst(FunctionType *Ty, Value *Func, const Twine &Name, diff --git a/llvm/lib/IR/Use.cpp b/llvm/lib/IR/Use.cpp --- a/llvm/lib/IR/Use.cpp +++ b/llvm/lib/IR/Use.cpp @@ -48,6 +48,13 @@ return this - getUser()->op_begin(); } +#ifndef NDEBUG +bool Use::checkDroppable() const { + return static_cast(Prev.getInt() & isDroppableMask) == + getUser()->isDroppable(); +} +#endif + // Sets up the waymarking algorithm's tags for a series of Uses. See the // algorithm details here: // @@ -94,7 +101,7 @@ const Use *Current = this; while (true) { - unsigned Tag = (Current++)->Prev.getInt(); + unsigned Tag = (Current++)->getTag(); switch (Tag) { case zeroDigitTag: case oneDigitTag: @@ -104,7 +111,7 @@ ++Current; ptrdiff_t Offset = 1; while (true) { - unsigned Tag = Current->Prev.getInt(); + unsigned Tag = Current->getTag(); switch (Tag) { case zeroDigitTag: case oneDigitTag: diff --git a/llvm/lib/IR/User.cpp b/llvm/lib/IR/User.cpp --- a/llvm/lib/IR/User.cpp +++ b/llvm/lib/IR/User.cpp @@ -109,9 +109,18 @@ bool User::isDroppable() const { if (const auto *Intr = dyn_cast(this)) return Intr->getIntrinsicID() == Intrinsic::assume; + /// If you are changing this definition you may need to add calls to + /// maybeMarkUsesAsDroppable in some subclasses return false; } +void User::maybeMarkUsesAsDroppable() { + if (!isDroppable()) + return; + for (unsigned i = 0; i < getNumOperands(); i++) + getOperandUse(i).setDroppable(); +} + //===----------------------------------------------------------------------===// // User operator new Implementations //===----------------------------------------------------------------------===// diff --git a/llvm/lib/IR/Value.cpp b/llvm/lib/IR/Value.cpp --- a/llvm/lib/IR/Value.cpp +++ b/llvm/lib/IR/Value.cpp @@ -141,33 +141,21 @@ return hasNItemsOrMore(use_begin(), use_end(), N); } -static bool isUnDroppableUser(const User *U) { return !U->isDroppable(); } - -Use *Value::getSingleUndroppableUse() { - Use *Result = nullptr; - for (Use &U : uses()) { - if (!U.getUser()->isDroppable()) { - if (Result) - return nullptr; - Result = &U; - } - } - return Result; -} +static bool isUnDroppableUse(const Use& U) { return !U.isDroppable(); } bool Value::hasNUndroppableUses(unsigned int N) const { - return hasNItems(user_begin(), user_end(), N, isUnDroppableUser); + return hasNItems(use_begin(), use_end(), N, isUnDroppableUse); } bool Value::hasNUndroppableUsesOrMore(unsigned int N) const { - return hasNItemsOrMore(user_begin(), user_end(), N, isUnDroppableUser); + return hasNItemsOrMore(use_begin(), use_end(), N, isUnDroppableUse); } void Value::dropDroppableUses( llvm::function_ref ShouldDrop) { SmallVector ToBeEdited; for (Use &U : uses()) - if (U.getUser()->isDroppable() && ShouldDrop(&U)) + if (U.isDroppable() && ShouldDrop(&U)) ToBeEdited.push_back(&U); for (Use *U : ToBeEdited) { U->removeFromList(); diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -4428,8 +4428,7 @@ /// See CaptureTracker::shouldExplore(...). bool shouldExplore(const Use *U) override { // Check liveness and ignore droppable users. - return !U->getUser()->isDroppable() && - !A.isAssumedDead(*U, &NoCaptureAA, &IsDeadAA); + return !U->isDroppable() && !A.isAssumedDead(*U, &NoCaptureAA, &IsDeadAA); } /// Update the state according to \p CapturedInMem, \p CapturedInInt, and @@ -7452,7 +7451,7 @@ LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n"); continue; } - if (U->getUser()->isDroppable()) { + if (U->isDroppable()) { LLVM_DEBUG(dbgs() << "[Attributor] Droppable user, skip!\n"); continue; }