[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

1352

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

1352

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

1352

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/lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueLattice.h"
 #include "llvm/Analysis/ValueLatticeUtils.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
class SCCPSolver : public InstVisitor<SCCPSolver> {
   DenseSet<Edge> KnownFeasibleEdges;
 
   DenseMap<Function *, AnalysisResultsForFn> AnalysisResults;
   DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
 
   LLVMContext &Ctx;
 
 public:
+  const DataLayout &getDataLayout() const { return DL; }
+
   void addAnalysis(Function &F, AnalysisResultsForFn A) {
     AnalysisResults.insert({&F, std::move(A)});
   }
 
   const PredicateBase *getPredicateInfoFor(Instruction *I) {
     auto A = AnalysisResults.find(I->getParent()->getParent());
     if (A == AnalysisResults.end())
       return nullptr;
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
         return;
       } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() &&
                  !MayIncludeUndef) {
         // Propagate inequalities.
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(IV, &CB,
                      ValueLatticeElement::getNot(CondVal.getConstant()));
         return;
       }
 
       return (void)mergeInValue(IV, &CB, CopyOfVal);
     }
   }
 
   // The common case is that we aren't tracking the callee, either because we
   // are not doing interprocedural analysis or the callee is indirect, or is
   // external.  Handle these cases first.
if (CI && CI->isMustTailCall() && !CI->isSafeToRemove()) {
     if (F)
       Solver.AddMustTailCallee(F);
 
     LLVM_DEBUG(dbgs() << "  Can\'t treat the result of musttail call : " << *CI
                       << " as a constant\n");
     return false;
   }
 
+  // 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 (Const->getType()->isPointerTy() &&
+      !canReplacePointersIfEqual(V, Const, Solver.getDataLayout(),
+                                 dyn_cast<Instruction>(V)))
+    return false;
+
   LLVM_DEBUG(dbgs() << "  Constant: " << *Const << " = " << *V << '\n');
 
   // Replaces all of the uses of a variable with uses of the constant.
   V->replaceAllUsesWith(Const);
   return true;
 }
 
 static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB,

llvm/test/Transforms/SCCP/apint-bigint2.ll

define i101 @large_aggregate_2() {
   %DD = or i101 %D, 1
   %F = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 5
   %G = getelementptr i101, i101* %F, i101 %DD
   %L3 = load i101, i101* %G
   ret i101 %L3
 }
 
 ; CHECK-LABEL: @index_too_large
-; CHECK-NEXT: store i101* getelementptr (i101, i101* getelementptr ([6 x i101], [6 x i101]* @Y, i32 0, i32 -1), i101 9224497936761618431), i101** undef
-; CHECK-NEXT: ret void
+; CHECK-NEXT:    %ptr1 = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 -1
+; CHECK-NEXT:    %ptr2 = getelementptr i101, i101* %ptr1, i101 9224497936761618431
+; CHECK-NEXT:    store i101* %ptr2, i101** undef
+; CHECK-NEXT:    ret void
 define void @index_too_large() {
   %ptr1 = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 -1
   %ptr2 = getelementptr i101, i101* %ptr1, i101 9224497936761618431
   store i101* %ptr2, i101** undef
   ret void
 }

llvm/test/Transforms/SCCP/indirectbr.ll

 
 ; Make sure we can eliminate what is in BB0 as we know that the indirectbr is going to BB1
 ; by looking through the casts. The casts should be folded away when they are visited
 ; before the indirectbr instruction.
 ;
 define void @indbrtest2() {
 ; CHECK-LABEL: @indbrtest2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK-NEXT:    [[B:%.*]] = inttoptr i64 ptrtoint (i8* blockaddress(@indbrtest2, [[BB1:%.*]]) to i64) to i8*
+; CHECK-NEXT:    [[C:%.*]] = bitcast i8* [[B]] to i8*
+; CHECK-NEXT:    br label [[BB1]]
 ; CHECK:       BB1:
 ; CHECK-NEXT:    call void @BB1_f()
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = ptrtoint i8* blockaddress(@indbrtest2, %BB1) to i64
   %b = inttoptr i64 %a to i8*
   %c = bitcast i8* %b to i8*

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 @eq_undereferenceable(i32* %p) {
 ; CHECK-LABEL: @eq_undereferenceable(
 ; 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)

 }
 
 define i1 @eq_undereferenceable_cmp_simp(i32* %p) {
 ; CHECK-LABEL: @eq_undereferenceable_cmp_simp(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_0:%.*]] = 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_0]], 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:    ret i1 true
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[CMP_2:%.*]] = 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:    ret i1 [[CMP_2]]
 ;
 entry:
   %cmp.0 = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
   br i1 %cmp.0, label %if.then, label %if.end