Introduce Value::stripPointerCastsSameRepresentation

[jdoerfert]

Summary

This patch allows current users of Value::stripPointerCasts() to force
the result of the function to have the same representation as the value
it was called on. This is useful in various cases, e.g., (non-)null
checks.

In this patch only a single call site was adjusted to fix an existing
misuse (which is hard to test). Uses in attribute deduction and other
areas, e.g., D60047, are to be expected.

For a discussion on this topic, please see [0].

[0] http://lists.llvm.org/pipermail/llvm-dev/2018-December/128423.html

[arsenm]

llvm/include/llvm/IR/Value.h

502

I think a separate function name would be more helpful, implemented with a hidden bool argument

[jdoerfert]

llvm/include/llvm/IR/Value.h

502

It depends on different things, including taste. I don't feel strong so I'd be fine with a new function as well. Two things to consider though:

Do we want to prevent as-cast stripping in other strip-casts scenarios as well?
This patch enables it for PSK_ZeroIndicesAndAliases but not for PSK_ZeroIndices and PSK_ZeroIndicesAndAliasesAndInvariantGroups. If the answer is yes, then we would end up with even more versions in the stripXXXX family (we have a bunch already).

Do we want to be able to set KeepBitPattern as the default in order for us to "guarantee" correctness and give people a way to opt-in? We can achieve this also if the new function would look through as-casts and stripPointerCasts wouldn't anymore.

[hfinkel]

llvm/include/llvm/IR/Value.h

502

If we want to be able to switch the default at some point, I certainly recommend something with a name so that we can find the various forms with grep (etc.). We can always add more forms as needed (or we can switch the argument type to an enum).

[jdoerfert]

llvm/include/llvm/IR/Value.h

502

If we want to be able to switch the default at some point, I certainly recommend something with a name so that we can find the various forms with grep (etc.).

Later, the easiest "switch situation" is with the default argument (= this patch), especially because of down-stream code. Adding a new function now will fix the behavior of the new function. Switching stripPointerCasts later would then require us to replace all uses or introduce yet another function as a way to look through as-casts.

We can always add more forms as needed (or we can switch the argument type to an enum).

Now I'm confused. Do you want an argument to stripPointerCasts or a new function which will have a fixed semantic wrt. as-casts. For the latter, we would introduce either: stripTrivialPointerCasts (= w/o as-casts) or stripAddressSpaceAndPointerCasts (= w/ as-casts) and make stripPointerCasts do the oposite.

[jdoerfert]

Use a new function for the new behavior

[jdoerfert]

ping

[aykevl]

To me (someone from outside LLVM), the "keep bit pattern" argument looks confusing. Pointer casts do not necessarily change the bit pattern? In fact, it seems to me that most pointer casts preserve the bit pattern but change the meaning of the pointer (example: address space 1 on AVR which points into flash instead of RAM - no bits are changed with an addrspacecast). Names like stripTrivialPointerCasts and stripAddressSpaceAndPointerCasts look much more obvious to me. Or did I miss the real intent of the change here?
In other words, I would suggest renaming stripPointerCastsSameBitPattern to stripTrivialPointerCasts.

[arsenm]

In D61607#1507580, @aykevl wrote:

To me (someone from outside LLVM), the "keep bit pattern" argument looks confusing. Pointer casts do not necessarily change the bit pattern? In fact, it seems to me that most pointer casts preserve the bit pattern but change the meaning of the pointer (example: address space 1 on AVR which points into flash instead of RAM - no bits are changed with an addrspacecast).

This isn't how the IR is defined. addrspacecast is explicitly allowed to change the bit pattern of the pointer, and it does for some addrspace combinations on some targets (like AMDGPU). It has to be assumed it could have changed the bitpattern without specific target information.

[aykevl]

Yes I know it can change the bit pattern. And if it is only about the bit pattern, the name is fine. However, it seems to me that the only difference between stripPointerCastsSameBitPattern and stripPointerCasts is the AS, which may or may not be relevant to the bit pattern. This is confusing: it isn't clear to me from the name stripPointerCastsSameBitPattern whether it may strip any addrspacecast that has the same bit pattern.

[arsenm]

In D61607#1507697, @aykevl wrote:

Yes I know it can change the bit pattern. And if it is only about the bit pattern, the name is fine. However, it seems to me that the only difference between stripPointerCastsSameBitPattern and stripPointerCasts is the AS, which may or may not be relevant to the bit pattern. This is confusing: it isn't clear to me from the name stripPointerCastsSameBitPattern whether it may strip any addrspacecast that has the same bit pattern.

I think bitcasts between equivalently sized pointers with different address spaces should be allowed, rather than requiring addrspacecast like today, so I'm not sure I would want to specify this is an address space property

[jdoerfert]

In D61607#1507697, @aykevl wrote:

Yes I know it can change the bit pattern. And if it is only about the bit pattern, the name is fine. However, it seems to me that the only difference between stripPointerCastsSameBitPattern and stripPointerCasts is the AS, which may or may not be relevant to the bit pattern. This is confusing: it isn't clear to me from the name stripPointerCastsSameBitPattern whether it may strip any addrspacecast that has the same bit pattern.

I think I do not understand the problem. For me, it is all about the bit-pattern. But in general, I think users should not care what casts are stripped and which are not. It should be clear from the name and description what they can expect. Maybe someone adds logic here to determine if as-casts preserve the bit pattern. That will help users that need the same bit pattern, e.g., the isNonNull family of calls, and it will break with the strict no-as rule. If we add another "as-cast-like" instruction (like D59065) that might change the bit-pattern but not the "logical object" users of any stripPointerCastsXXX call should get the right value.

[hfinkel]

In D61607#1509496, @jdoerfert wrote:

In D61607#1507697, @aykevl wrote:

Yes I know it can change the bit pattern. And if it is only about the bit pattern, the name is fine. However, it seems to me that the only difference between stripPointerCastsSameBitPattern and stripPointerCasts is the AS, which may or may not be relevant to the bit pattern. This is confusing: it isn't clear to me from the name stripPointerCastsSameBitPattern whether it may strip any addrspacecast that has the same bit pattern.

I think I do not understand the problem. For me, it is all about the bit-pattern. But in general, I think users should not care what casts are stripped and which are not. It should be clear from the name and description what they can expect. Maybe someone adds logic here to determine if as-casts preserve the bit pattern. That will help users that need the same bit pattern, e.g., the isNonNull family of calls, and it will break with the strict no-as rule. If we add another "as-cast-like" instruction (like D59065) that might change the bit-pattern but not the "logical object" users of any stripPointerCastsXXX call should get the right value.

I agree with this. I recall past conversations about adding something to DataLayout to say that some address-space pairs share the same pointer representation, or some aspects of the representation, I don't know if we ever had a strong-enough use case to write the code, but should such a worthwhile case emerge, I can certainly see us teaching the optimizer that some as-casts don't change (certain relevant aspects of) the underlying representation.

As a bit of bikeshedding, I like the term 'representation' better than 'pattern'. I wonder if the name stripPointerCastsSameIntRepresentation would be clearer? (The idea being that pointers are opaque types at the IR level, but get integer representations via ptrtoint).

[arsenm]

In D61607#1510300, @hfinkel wrote:

I agree with this. I recall past conversations about adding something to DataLayout to say that some address-space pairs share the same pointer representation, or some aspects of the representation, I don't know if we ever had a strong-enough use case to write the code, but should such a worthwhile case emerge, I can certainly see us teaching the optimizer that some as-casts don't change (certain relevant aspects of) the underlying representation.

I'd like to allow bitcasts between pointers with the same size for this purpose

As a bit of bikeshedding, I like the term 'representation' better than 'pattern'. I wonder if the name stripPointerCastsSameIntRepresentation would be clearer? (The idea being that pointers are opaque types at the IR level, but get integer representations via ptrtoint).

There are non-integral pointers, so I don't think the name should refer to integers

[hfinkel]

In D61607#1510395, @arsenm wrote:

In D61607#1510300, @hfinkel wrote:

I agree with this. I recall past conversations about adding something to DataLayout to say that some address-space pairs share the same pointer representation, or some aspects of the representation, I don't know if we ever had a strong-enough use case to write the code, but should such a worthwhile case emerge, I can certainly see us teaching the optimizer that some as-casts don't change (certain relevant aspects of) the underlying representation.

I'd like to allow bitcasts between pointers with the same size for this purpose

As a bit of bikeshedding, I like the term 'representation' better than 'pattern'. I wonder if the name stripPointerCastsSameIntRepresentation would be clearer? (The idea being that pointers are opaque types at the IR level, but get integer representations via ptrtoint).

There are non-integral pointers, so I don't think the name should refer to integers

Good point. I'll revise my suggestion stripPointerCastsSameRepresentation.

[jdoerfert]

In D61607#1510412, @hfinkel wrote:

In D61607#1510395, @arsenm wrote:

In D61607#1510300, @hfinkel wrote:

I agree with this. I recall past conversations about adding something to DataLayout to say that some address-space pairs share the same pointer representation, or some aspects of the representation, I don't know if we ever had a strong-enough use case to write the code, but should such a worthwhile case emerge, I can certainly see us teaching the optimizer that some as-casts don't change (certain relevant aspects of) the underlying representation.

I'd like to allow bitcasts between pointers with the same size for this purpose

As a bit of bikeshedding, I like the term 'representation' better than 'pattern'. I wonder if the name stripPointerCastsSameIntRepresentation would be clearer? (The idea being that pointers are opaque types at the IR level, but get integer representations via ptrtoint).

There are non-integral pointers, so I don't think the name should refer to integers

Good point. I'll revise my suggestion stripPointerCastsSameRepresentation.

I don't want to argue about the name at this point. I gladly change it if I get a LGTM with the name change request. (@arsenm?)

[arsenm]

In D61607#1511408, @jdoerfert wrote:

In D61607#1510412, @hfinkel wrote:

In D61607#1510395, @arsenm wrote:

In D61607#1510300, @hfinkel wrote:

I agree with this. I recall past conversations about adding something to DataLayout to say that some address-space pairs share the same pointer representation, or some aspects of the representation, I don't know if we ever had a strong-enough use case to write the code, but should such a worthwhile case emerge, I can certainly see us teaching the optimizer that some as-casts don't change (certain relevant aspects of) the underlying representation.

I'd like to allow bitcasts between pointers with the same size for this purpose

As a bit of bikeshedding, I like the term 'representation' better than 'pattern'. I wonder if the name stripPointerCastsSameIntRepresentation would be clearer? (The idea being that pointers are opaque types at the IR level, but get integer representations via ptrtoint).

There are non-integral pointers, so I don't think the name should refer to integers

Good point. I'll revise my suggestion stripPointerCastsSameRepresentation.

I don't want to argue about the name at this point. I gladly change it if I get a LGTM with the name change request. (@arsenm?)

+1

[jdoerfert]

In D61607#1515069, @arsenm wrote:

In D61607#1511408, @jdoerfert wrote:

In D61607#1510412, @hfinkel wrote:

In D61607#1510395, @arsenm wrote:

In D61607#1510300, @hfinkel wrote:

I agree with this. I recall past conversations about adding something to DataLayout to say that some address-space pairs share the same pointer representation, or some aspects of the representation, I don't know if we ever had a strong-enough use case to write the code, but should such a worthwhile case emerge, I can certainly see us teaching the optimizer that some as-casts don't change (certain relevant aspects of) the underlying representation.

I'd like to allow bitcasts between pointers with the same size for this purpose

As a bit of bikeshedding, I like the term 'representation' better than 'pattern'. I wonder if the name stripPointerCastsSameIntRepresentation would be clearer? (The idea being that pointers are opaque types at the IR level, but get integer representations via ptrtoint).

There are non-integral pointers, so I don't think the name should refer to integers

Good point. I'll revise my suggestion stripPointerCastsSameRepresentation.

I don't want to argue about the name at this point. I gladly change it if I get a LGTM with the name change request. (@arsenm?)

+1

Should I take this as "LGTM with the name change" or as a "name change seems fine, someone else needs to sign-off"? (I will also adjust the commit message accordingly)

[jdoerfert]

Rename method and rephrase commit message

[hfinkel]

LGTM

llvm/include/llvm/IR/Value.h

#include "llvm/IR/Value.def"
   bool isUsedByMetadata() const { return IsUsedByMD; }
 
   /// Return true if this value is a swifterror value.
   ///
   /// swifterror values can be either a function argument or an alloca with a
   /// swifterror attribute.
   bool isSwiftError() const;
 
-  /// Strip off pointer casts, all-zero GEPs, and aliases.
+  /// Strip off pointer casts, all-zero GEPs, address space casts, and aliases.
   ///
   /// Returns the original uncasted value.  If this is called on a non-pointer
   /// value, it returns 'this'.
   const Value *stripPointerCasts() const;
   Value *stripPointerCasts() {
     return const_cast<Value *>(
                          static_cast<const Value *>(this)->stripPointerCasts());
   }
 
+  /// Strip off pointer casts, all-zero GEPs, address space casts, and aliases
+  /// but ensures the representation of the result stays the same.
+  ///
+  /// Returns the original uncasted value with the same representation. If this
+  /// is called on a non-pointer value, it returns 'this'.
+  const Value *stripPointerCastsSameRepresentation() const;
+  Value *stripPointerCastsSameRepresentation() {
+    return const_cast<Value *>(static_cast<const Value *>(this)
+                                   ->stripPointerCastsSameRepresentation());
+  }
+
   /// Strip off pointer casts, all-zero GEPs, aliases and invariant group
   /// info.
   ///
   /// Returns the original uncasted value.  If this is called on a non-pointer
   /// value, it returns 'this'. This function should be used only in
   /// Alias analysis.
   const Value *stripPointerCastsAndInvariantGroups() const;
   Value *stripPointerCastsAndInvariantGroups() {

llvm/lib/Analysis/LazyValueInfo.cpp

 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
                               Instruction *CxtI) {
   // Is or is not NonNull are common predicates being queried. If
   // isKnownNonZero can tell us the result of the predicate, we can
   // return it quickly. But this is only a fastpath, and falling
   // through would still be correct.
   const DataLayout &DL = CxtI->getModule()->getDataLayout();
   if (V->getType()->isPointerTy() && C->isNullValue() &&
-      isKnownNonZero(V->stripPointerCasts(), DL)) {
+      isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)) {
     if (Pred == ICmpInst::ICMP_EQ)
       return LazyValueInfo::False;
     else if (Pred == ICmpInst::ICMP_NE)
       return LazyValueInfo::True;
   }
   ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
   if (Ret != Unknown)

llvm/lib/IR/Value.cpp

void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
   }
 }
 
 namespace {
 // Various metrics for how much to strip off of pointers.
 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
+  PSK_ZeroIndicesAndAliasesSameRepresentation,
   PSK_ZeroIndicesAndAliasesAndInvariantGroups,
   PSK_InBoundsConstantIndices,
   PSK_InBounds
 };
 
 template <PointerStripKind StripKind>
 static const Value *stripPointerCastsAndOffsets(const Value *V) {
   if (!V->getType()->isPointerTy())
     return V;
 
   // Even though we don't look through PHI nodes, we could be called on an
   // instruction in an unreachable block, which may be on a cycle.
   SmallPtrSet<const Value *, 4> Visited;
 
   Visited.insert(V);
   do {
     if (auto *GEP = dyn_cast<GEPOperator>(V)) {
       switch (StripKind) {
       case PSK_ZeroIndicesAndAliases:
+      case PSK_ZeroIndicesAndAliasesSameRepresentation:
       case PSK_ZeroIndicesAndAliasesAndInvariantGroups:
       case PSK_ZeroIndices:
         if (!GEP->hasAllZeroIndices())
           return V;
         break;
       case PSK_InBoundsConstantIndices:
         if (!GEP->hasAllConstantIndices())
           return V;
         LLVM_FALLTHROUGH;
       case PSK_InBounds:
         if (!GEP->isInBounds())
           return V;
         break;
       }
       V = GEP->getPointerOperand();
-    } else if (Operator::getOpcode(V) == Instruction::BitCast ||
+    } else if (Operator::getOpcode(V) == Instruction::BitCast) {
+      V = cast<Operator>(V)->getOperand(0);
+    } else if (StripKind != PSK_ZeroIndicesAndAliasesSameRepresentation &&
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
+      // TODO: If we know an address space cast will not change the
+      //       representation we could look through it here as well.
       V = cast<Operator>(V)->getOperand(0);
     } else if (auto *GA = dyn_cast<GlobalAlias>(V)) {
       if (StripKind == PSK_ZeroIndices || GA->isInterposable())
         return V;
       V = GA->getAliasee();
     } else {
       if (const auto *Call = dyn_cast<CallBase>(V)) {
         if (const Value *RV = Call->getReturnedArgOperand()) {
static const Value *stripPointerCastsAndOffsets(const Value *V) {
   return V;
 }
 } // end anonymous namespace
 
 const Value *Value::stripPointerCasts() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
 }
 
+const Value *Value::stripPointerCastsSameRepresentation() const {
+  return stripPointerCastsAndOffsets<
+      PSK_ZeroIndicesAndAliasesSameRepresentation>(this);
+}
+
 const Value *Value::stripPointerCastsNoFollowAliases() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
 }
 
 const Value *Value::stripInBoundsConstantOffsets() const {
   return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
 }