summaryrefslogtreecommitdiff
path: root/include/llvm/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/Analysis')
-rw-r--r--include/llvm/Analysis/MemorySSA.h113
-rw-r--r--include/llvm/Analysis/ScalarEvolution.h26
-rw-r--r--include/llvm/Analysis/TargetLibraryInfo.h13
-rw-r--r--include/llvm/Analysis/ValueTracking.h37
4 files changed, 137 insertions, 52 deletions
diff --git a/include/llvm/Analysis/MemorySSA.h b/include/llvm/Analysis/MemorySSA.h
index db31ae9f4f10..f0bba8c4c020 100644
--- a/include/llvm/Analysis/MemorySSA.h
+++ b/include/llvm/Analysis/MemorySSA.h
@@ -84,6 +84,7 @@
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/DerivedUser.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/OperandTraits.h"
@@ -127,7 +128,7 @@ using const_memoryaccess_def_iterator =
// \brief The base for all memory accesses. All memory accesses in a block are
// linked together using an intrusive list.
class MemoryAccess
- : public User,
+ : public DerivedUser,
public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
public:
@@ -145,15 +146,14 @@ public:
MemoryAccess(const MemoryAccess &) = delete;
MemoryAccess &operator=(const MemoryAccess &) = delete;
- ~MemoryAccess() override;
void *operator new(size_t, unsigned) = delete;
void *operator new(size_t) = delete;
BasicBlock *getBlock() const { return Block; }
- virtual void print(raw_ostream &OS) const = 0;
- virtual void dump() const;
+ void print(raw_ostream &OS) const;
+ void dump() const;
/// \brief The user iterators for a memory access
typedef user_iterator iterator;
@@ -207,11 +207,12 @@ protected:
/// \brief Used for debugging and tracking things about MemoryAccesses.
/// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
- virtual unsigned getID() const = 0;
+ inline unsigned getID() const;
- MemoryAccess(LLVMContext &C, unsigned Vty, BasicBlock *BB,
- unsigned NumOperands)
- : User(Type::getVoidTy(C), Vty, nullptr, NumOperands), Block(BB) {}
+ MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
+ BasicBlock *BB, unsigned NumOperands)
+ : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),
+ Block(BB) {}
private:
BasicBlock *Block;
@@ -248,21 +249,21 @@ public:
// Sadly, these have to be public because they are needed in some of the
// iterators.
- virtual bool isOptimized() const = 0;
- virtual MemoryAccess *getOptimized() const = 0;
- virtual void setOptimized(MemoryAccess *) = 0;
+ inline bool isOptimized() const;
+ inline MemoryAccess *getOptimized() const;
+ inline void setOptimized(MemoryAccess *);
/// \brief Reset the ID of what this MemoryUse was optimized to, causing it to
/// be rewalked by the walker if necessary.
/// This really should only be called by tests.
- virtual void resetOptimized() = 0;
+ inline void resetOptimized();
protected:
friend class MemorySSA;
friend class MemorySSAUpdater;
MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
- Instruction *MI, BasicBlock *BB)
- : MemoryAccess(C, Vty, BB, 1), MemoryInst(MI) {
+ DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB)
+ : MemoryAccess(C, Vty, DeleteValue, BB, 1), MemoryInst(MI) {
setDefiningAccess(DMA);
}
void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false) {
@@ -292,7 +293,8 @@ public:
DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
- : MemoryUseOrDef(C, DMA, MemoryUseVal, MI, BB), OptimizedID(0) {}
+ : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB),
+ OptimizedID(0) {}
// allocate space for exactly one operand
void *operator new(size_t s) { return User::operator new(s, 1); }
@@ -302,32 +304,30 @@ public:
return MA->getValueID() == MemoryUseVal;
}
- void print(raw_ostream &OS) const override;
+ void print(raw_ostream &OS) const;
- virtual void setOptimized(MemoryAccess *DMA) override {
+ void setOptimized(MemoryAccess *DMA) {
OptimizedID = DMA->getID();
setOperand(0, DMA);
}
- virtual bool isOptimized() const override {
+ bool isOptimized() const {
return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
}
- virtual MemoryAccess *getOptimized() const override {
+ MemoryAccess *getOptimized() const {
return getDefiningAccess();
}
- virtual void resetOptimized() override {
+ void resetOptimized() {
OptimizedID = INVALID_MEMORYACCESS_ID;
}
protected:
friend class MemorySSA;
- unsigned getID() const override {
- llvm_unreachable("MemoryUses do not have IDs");
- }
-
private:
+ static void deleteMe(DerivedUser *Self);
+
unsigned int OptimizedID;
};
@@ -350,8 +350,8 @@ public:
MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
unsigned Ver)
- : MemoryUseOrDef(C, DMA, MemoryDefVal, MI, BB), ID(Ver),
- Optimized(nullptr), OptimizedID(INVALID_MEMORYACCESS_ID) {}
+ : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB),
+ ID(Ver), Optimized(nullptr), OptimizedID(INVALID_MEMORYACCESS_ID) {}
// allocate space for exactly one operand
void *operator new(size_t s) { return User::operator new(s, 1); }
@@ -361,27 +361,28 @@ public:
return MA->getValueID() == MemoryDefVal;
}
- virtual void setOptimized(MemoryAccess *MA) override {
+ void setOptimized(MemoryAccess *MA) {
Optimized = MA;
OptimizedID = getDefiningAccess()->getID();
}
- virtual MemoryAccess *getOptimized() const override { return Optimized; }
- virtual bool isOptimized() const override {
+ MemoryAccess *getOptimized() const { return Optimized; }
+ bool isOptimized() const {
return getOptimized() && getDefiningAccess() &&
OptimizedID == getDefiningAccess()->getID();
}
- virtual void resetOptimized() override {
+ void resetOptimized() {
OptimizedID = INVALID_MEMORYACCESS_ID;
}
- void print(raw_ostream &OS) const override;
+ void print(raw_ostream &OS) const;
-protected:
friend class MemorySSA;
- unsigned getID() const override { return ID; }
+ unsigned getID() const { return ID; }
private:
+ static void deleteMe(DerivedUser *Self);
+
const unsigned ID;
MemoryAccess *Optimized;
unsigned int OptimizedID;
@@ -432,7 +433,8 @@ public:
DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
- : MemoryAccess(C, MemoryPhiVal, BB, 0), ID(Ver), ReservedSpace(NumPreds) {
+ : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
+ ReservedSpace(NumPreds) {
allocHungoffUses(ReservedSpace);
}
@@ -534,7 +536,9 @@ public:
return V->getValueID() == MemoryPhiVal;
}
- void print(raw_ostream &OS) const override;
+ void print(raw_ostream &OS) const;
+
+ unsigned getID() const { return ID; }
protected:
friend class MemorySSA;
@@ -546,8 +550,6 @@ protected:
User::allocHungoffUses(N, /* IsPhi */ true);
}
- unsigned getID() const final { return ID; }
-
private:
// For debugging only
const unsigned ID;
@@ -561,8 +563,45 @@ private:
ReservedSpace = std::max(E + E / 2, 2u);
growHungoffUses(ReservedSpace, /* IsPhi */ true);
}
+
+ static void deleteMe(DerivedUser *Self);
};
+inline unsigned MemoryAccess::getID() const {
+ assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
+ "only memory defs and phis have ids");
+ if (const auto *MD = dyn_cast<MemoryDef>(this))
+ return MD->getID();
+ return cast<MemoryPhi>(this)->getID();
+}
+
+inline bool MemoryUseOrDef::isOptimized() const {
+ if (const auto *MD = dyn_cast<MemoryDef>(this))
+ return MD->isOptimized();
+ return cast<MemoryUse>(this)->isOptimized();
+}
+
+inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
+ if (const auto *MD = dyn_cast<MemoryDef>(this))
+ return MD->getOptimized();
+ return cast<MemoryUse>(this)->getOptimized();
+}
+
+inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
+ if (auto *MD = dyn_cast<MemoryDef>(this))
+ MD->setOptimized(MA);
+ else
+ cast<MemoryUse>(this)->setOptimized(MA);
+}
+
+inline void MemoryUseOrDef::resetOptimized() {
+ if (auto *MD = dyn_cast<MemoryDef>(this))
+ MD->resetOptimized();
+ else
+ cast<MemoryUse>(this)->resetOptimized();
+}
+
+
template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index ceca6cb389a1..ac54bd4cfffb 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -656,10 +656,12 @@ private:
/// Test whether this BackedgeTakenInfo contains complete information.
bool hasFullInfo() const { return isComplete(); }
- /// Return an expression indicating the exact backedge-taken count of the
- /// loop if it is known or SCEVCouldNotCompute otherwise. This is the
- /// number of times the loop header can be guaranteed to execute, minus
- /// one.
+ /// Return an expression indicating the exact *backedge-taken*
+ /// count of the loop if it is known or SCEVCouldNotCompute
+ /// otherwise. If execution makes it to the backedge on every
+ /// iteration (i.e. there are no abnormal exists like exception
+ /// throws and thread exits) then this is the number of times the
+ /// loop header will execute minus one.
///
/// If the SCEV predicate associated with the answer can be different
/// from AlwaysTrue, we must add a (non null) Predicates argument.
@@ -1398,11 +1400,11 @@ public:
const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
/// If the specified loop has a predictable backedge-taken count, return it,
- /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count
- /// is the number of times the loop header will be branched to from within
- /// the loop. This is one less than the trip count of the loop, since it
- /// doesn't count the first iteration, when the header is branched to from
- /// outside the loop.
+ /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
+ /// the number of times the loop header will be branched to from within the
+ /// loop, assuming there are no abnormal exists like exception throws. This is
+ /// one less than the trip count of the loop, since it doesn't count the first
+ /// iteration, when the header is branched to from outside the loop.
///
/// Note that it is not valid to call this method on a loop without a
/// loop-invariant backedge-taken count (see
@@ -1417,8 +1419,10 @@ public:
const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
SCEVUnionPredicate &Predicates);
- /// Similar to getBackedgeTakenCount, except return the least SCEV value
- /// that is known never to be less than the actual backedge taken count.
+ /// When successful, this returns a SCEVConstant that is greater than or equal
+ /// to (i.e. a "conservative over-approximation") of the value returend by
+ /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
+ /// SCEVCouldNotCompute object.
const SCEV *getMaxBackedgeTakenCount(const Loop *L);
/// Return true if the backedge taken count is either the value returned by
diff --git a/include/llvm/Analysis/TargetLibraryInfo.h b/include/llvm/Analysis/TargetLibraryInfo.h
index 944250cfd6ac..0e3bdaa11c9a 100644
--- a/include/llvm/Analysis/TargetLibraryInfo.h
+++ b/include/llvm/Analysis/TargetLibraryInfo.h
@@ -191,6 +191,14 @@ public:
void setShouldSignExtI32Param(bool Val) {
ShouldSignExtI32Param = Val;
}
+
+ /// Returns the size of the wchar_t type in bytes.
+ unsigned getWCharSize(const Module &M) const;
+
+ /// Returns size of the default wchar_t type on target \p T. This is mostly
+ /// intended to verify that the size in the frontend matches LLVM. All other
+ /// queries should use getWCharSize() instead.
+ static unsigned getTargetWCharSize(const Triple &T);
};
/// Provides information about what library functions are available for
@@ -307,6 +315,11 @@ public:
return Attribute::None;
}
+ /// \copydoc TargetLibraryInfoImpl::getWCharSize()
+ unsigned getWCharSize(const Module &M) const {
+ return Impl->getWCharSize(M);
+ }
+
/// Handle invalidation from the pass manager.
///
/// If we try to invalidate this info, just return false. It cannot become
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index f5f323c6b797..cf24062e46f8 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -218,9 +218,38 @@ template <typename T> class ArrayRef;
DL);
}
- /// Returns true if the GEP is based on a pointer to a string (array of i8),
- /// and is indexing into this string.
- bool isGEPBasedOnPointerToString(const GEPOperator *GEP);
+ /// Returns true if the GEP is based on a pointer to a string (array of
+ // \p CharSize integers) and is indexing into this string.
+ bool isGEPBasedOnPointerToString(const GEPOperator *GEP,
+ unsigned CharSize = 8);
+
+ /// Represents offset+length into a ConstantDataArray.
+ struct ConstantDataArraySlice {
+ /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
+ /// initializer, it just doesn't fit the ConstantDataArray interface).
+ const ConstantDataArray *Array;
+ /// Slice starts at this Offset.
+ uint64_t Offset;
+ /// Length of the slice.
+ uint64_t Length;
+
+ /// Moves the Offset and adjusts Length accordingly.
+ void move(uint64_t Delta) {
+ assert(Delta < Length);
+ Offset += Delta;
+ Length -= Delta;
+ }
+ /// Convenience accessor for elements in the slice.
+ uint64_t operator[](unsigned I) const {
+ return Array==nullptr ? 0 : Array->getElementAsInteger(I + Offset);
+ }
+ };
+
+ /// Returns true if the value \p V is a pointer into a ContantDataArray.
+ /// If successfull \p Index will point to a ConstantDataArray info object
+ /// with an apropriate offset.
+ bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice,
+ unsigned ElementSize, uint64_t Offset = 0);
/// This function computes the length of a null-terminated C string pointed to
/// by V. If successful, it returns true and returns the string in Str. If
@@ -233,7 +262,7 @@ template <typename T> class ArrayRef;
/// If we can compute the length of the string pointed to by the specified
/// pointer, return 'len+1'. If we can't, return 0.
- uint64_t GetStringLength(const Value *V);
+ uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
/// This method strips off any GEP address adjustments and pointer casts from
/// the specified value, returning the original object being addressed. Note
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-05 11:20:39 +0000