[SCCP] Do not replace deref'able ptr with un-deref'able one.

[fhahn]

Summary

Currently IPSCCP (and others like CVP/GVN) blindly propagate pointer
equalities. In certain cases, that leads to dereferenceable pointers
being replaced, as in the example test case.

I think this is not allowed, as it introduces an access of an
un-dereferenceable pointer. Note that the pointer is inbounds, but one
past the last element, so it is valid, but not dereferenceable.

This patch is mostly to highlight the issue and start a discussion.
Currently it only checks for specifically looking
one-past-the-last-element pointers with array typed bases.

This causes the mis-compile outlined in
https://stackoverflow.com/questions/55754313/is-this-gcc-clang-past-one-pointer-comparison-behavior-conforming-or-non-standar

In the test case, if we replace %p with the GEP for the store, we
subsequently determine that the store and the load cannot alias, because
they are to different underlying objects.

Note that Alive2 seems to think that the replacement is valid:
https://alive2.llvm.org/ce/z/2rorhk

[aqjune]

Note that Alive2 seems to think that the replacement is valid:
https://alive2.llvm.org/ce/z/2rorhk

This is because Alive2's pointer comparison is approximating its behavior yet; it is right that we cannot replace a pointer with another pointer in general.

[efriedma]

LLVM's memory model isn't completely settled with respect to how to determine the "base" of a pointer; see https://bugs.llvm.org/show_bug.cgi?id=34548 etc. But consensus is that the general transform you're describing isn't legal without proving more about the pointer. (e.g. that the two pointers have the same base, or the replaced value isn't used for any memory operations).

llvm/lib/Transforms/Scalar/SCCP.cpp

1357

I'm not sure I completely follow what this code is doing, but using getPointerElementType() like this is probably wrong.

[fhahn]

In D85332#2197623, @efriedma wrote:

LLVM's memory model isn't completely settled with respect to how to determine the "base" of a pointer; see https://bugs.llvm.org/show_bug.cgi?id=34548 etc. But consensus is that the general transform you're describing isn't legal without proving more about the pointer. (e.g. that the two pointers have the same base, or the replaced value isn't used for any memory operations).

Great, thanks for the reference.

This patch is aimed as a first step towards incrementally improving the current situation by avoiding replacements for which there is agreement that they are problematic. The narrow initial case would be replacing a dereferenceable pointer with a clearly un-dereferenceable one.

If there is consensus on the approach, I think it would make sense to adjust the patch roughly as follows:

1. Add a canReplaceDueToPointerEqualilty(Ptr1, Ptr2) which returns true if we can replace Ptr1 with Ptr2 if they are considered equal or false if not.
2. The initial implementation will be incomplete and only reject certain cases (rather than only allowing cases we know are fine (e.g. both pointers dereferenceable and from the same underlying object)
3. Update GVN/SCCP/CPV to use canReplaceDueToPointerEqualilty.

Does that make sense?

llvm/lib/Transforms/Scalar/SCCP.cpp

1357

My intention here is to catch the case where we create a pointer to the 'one-past-the-last-element', which clearly is not dereferenceable.

As implemented above, it probably only works for GEPs with pointers to array types as bases. So this would need further refinement to make sure we actually use the right base when dealing with nested data types. Is that what you were referring to or is there something else I am missing? Do you know if there are any helpful utilities for doing such a thing?

[efriedma]

llvm/lib/Transforms/Scalar/SCCP.cpp

1357

The simplest correct check I can think of is that you could DecomposeGEPExpression both sides of the equality, and check if the "Base" is equal. That should cover everything, barring any weirdness with noalias/argmemonly/etc.

The problem here isn't really restricted to one-past-the-end. Consider, for example, if you call malloc, then free the memory, then call malloc again. The two pointers can be equal, but don't point to the same object.

[fhahn]

Updated to use canReplacePointersIfEqual, only guard the actual replacement, which still allows for simplification of conditionals based on equality.

[fhahn]

ping

[efriedma]

LGTM

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

public:
 
   /// Returns the behavior when calling the given call site.
   FunctionModRefBehavior getModRefBehavior(const CallBase *Call);
 
   /// Returns the behavior when calling the given function. For use when the
   /// call site is not known.
   FunctionModRefBehavior getModRefBehavior(const Function *Fn);
 
-private:
   // A linear transformation of a Value; this class represents ZExt(SExt(V,
   // SExtBits), ZExtBits) * Scale + Offset.
   struct VariableGEPIndex {
     // An opaque Value - we can't decompose this further.
     const Value *V;
 
     // We need to track what extensions we've done as we consider the same Value
     // with different extensions as different variables in a GEP's linear
public:
   GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
                       unsigned &ZExtBits, unsigned &SExtBits,
                       const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
                       DominatorTree *DT, bool &NSW, bool &NUW);
 
   static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed,
       const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT);
 
+private:
   static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
       const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
       LocationSize ObjectAccessSize);
 
   /// A Heuristic for aliasGEP that searches for a constant offset
   /// between the variables.
   ///
   /// GetLinearExpression has some limitations, as generally zext(%x + 1)

llvm/lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueLattice.h"
 #include "llvm/Analysis/ValueLatticeUtils.h"
 #include "llvm/Analysis/ValueTracking.h"
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
                        getMaxWidenStepsOpts());
         }
       } else
         mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts());
     }
   }
 }
 
+static unsigned getMaxPointerSize(const DataLayout &DL) {
+  unsigned MaxPointerSize = DL.getMaxPointerSizeInBits();
+  if (MaxPointerSize < 64)
+    MaxPointerSize = 64;
+
+  return MaxPointerSize;
+}
+
 void SCCPSolver::handleCallResult(CallBase &CB) {
   Function *F = CB.getCalledFunction();
 
   if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
     if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       if (ValueState[&CB].isOverdefined())
         return;
 
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
           NewCR = CopyOfCR;
 
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(
             IV, &CB,
             ValueLatticeElement::getRange(NewCR, MayIncludeUndef));
         return;
       } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
+        Constant *C = CondVal.getConstant();
+
+        // Do not propagate equality of a un-dereferenceable pointer.
+        // FIXME: Currently this only treats pointers one past the last element
+        // for array types. Should probably be much stricter.
+        if (C->getType()->isPointerTy()) {
+          BasicAAResult::DecomposedGEP Dec;
+          unsigned MaxPointerSize = getMaxPointerSize(DL);
+          Dec.StructOffset = Dec.OtherOffset = APInt(MaxPointerSize, 0);
+          Dec.StructOffset = Dec.OtherOffset = APInt(MaxPointerSize, 0);
+
+          BasicAAResult::DecomposeGEPExpression(C, Dec, DL, nullptr, nullptr);
+          auto *BaseTy = Dec.Base->getType()->getPointerElementType();
+          if (BaseTy->isArrayTy() &&
+              DL.getTypeSizeInBits(
+                  Dec.Base->getType()->getPointerElementType()) /
+                      8 ==
+                  Dec.OtherOffset) {
+            return (void)mergeInValue(IV, &CB, CopyOfVal);
+          }
+        }
         // For non-integer values or integer constant expressions, only
         // propagate equal constants.
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(IV, &CB, CondVal);
         return;
       } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() &&
                  !MayIncludeUndef) {
         // Propagate inequalities.

llvm/test/Transforms/SCCP/replace-dereferenceable-ptr-with-undereferenceable.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -ipsccp -S %s | FileCheck %s
 
 @y = common global [1 x i32] zeroinitializer, align 4
 @x = common global [1 x i32] zeroinitializer, align 4
 
 define i32 @test1(i32* %p) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i32 1, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0), align 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32* [[P:%.*]], getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 2, i32* getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1), align 4
+; CHECK-NEXT:    store i32 2, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0), align 4
 ; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   store i32 1, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0), align 4
   %cmp = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)