[InstSimplify] Use canReplacePointersIfEqual to conditionally simplify '(ptr1 == ptr2) ? a : b'

[aqjune]

Summary

InstSimplify has a folding

(x == y ? a : b) => b

that is valid if the equality can lead to the conclusion.
However, if x and y are pointers, the condition must be more restrictive because x == y being true does not imply that they are truly equivalent values.

This patch fixes InstSimplify to conditionally perform the transformation if they are pointers, using canReplacePointersIfEqual.

[aqjune]

llvm/lib/Analysis/InstructionSimplify.cpp

4348

Refinement must not be used in this case; AreEqual is used instead therefore.

llvm/test/Transforms/InstSimplify/select-ptr-eq.ll

44

case3 and case4 are kept optimized.

[aqjune]

I began to think that we might not need to make replacement of pointers 'directional' because it is too complex.
What about renaming canReplacePointersIfEqual in Loads.h to haveSameProvenance and only checking the equivalence of two pointers, which will make things simpler (including this patch)?

In theory, if inttoptr is involved, pointer replacement might be directional (it depends on the semantics of inttoptr); but we don't need to get that deep ATM.

[aqjune]

haveSameProvenanceIfEqual seems like a better name, certainly.

llvm/include/llvm/Analysis/Loads.h

 
 /// Returns true if a pointer value \p A can be replace with another pointer
 /// value \B if they are deemed equal through some means (e.g. information from
 /// conditions).
 /// NOTE: the current implementations is incomplete and unsound. It does not
 /// reject all invalid cases yet, but will be made stricter in the future. In
 /// particular this means returning true means unknown if replacement is safe.
 bool canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
-                               Instruction *CtxI);
+                               const Instruction *CtxI);
 }
 
 #endif

llvm/lib/Analysis/InstructionSimplify.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/CmpInstAnalysis.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstSimplifyFolder.h"
+#include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/OverflowInstAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, CmpRHS, Pred,
     return V;
 
   // If we have a scalar equality comparison, then we know the value in one of
   // the arms of the select. See if substituting this value into the arm and
   // simplifying the result yields the same value as the other arm.
   // Note that the equivalence/replacement opportunity does not hold for vectors
   // because each element of a vector select is chosen independently.
   if (Pred == ICmpInst::ICMP_EQ && !CondVal->getType()->isVectorTy()) {
-    if (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q,
-                               /* AllowRefinement */ false, MaxRecurse) ==
-            TrueVal ||
+    // In the case of pointers, even if two pointers are compared equal,
+    // they are not truly the same value.
+    // We need to check using canReplacePointersIfEqual if CmpLHS can be
+    // replaced with CmpRHS and vice versa.
+    bool CanReplaceLWithR =
+        !CmpLHS->getType()->isPointerTy() ||
+        canReplacePointersIfEqual(CmpLHS, CmpRHS, Q.DL, Q.CxtI);
+    bool CanReplaceRWithL =
+        !CmpLHS->getType()->isPointerTy() ||
+        canReplacePointersIfEqual(CmpRHS, CmpLHS, Q.DL, Q.CxtI);
+    bool AreEqual = CanReplaceLWithR && CanReplaceRWithL;
+
+    if (AreEqual && (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q,
+                                            /* AllowRefinement */ false,
+                                            MaxRecurse) == TrueVal ||
                      simplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q,
-                               /* AllowRefinement */ false, MaxRecurse) ==
-            TrueVal)
+                                            /* AllowRefinement */ false,
+                                            MaxRecurse) == TrueVal))
       return FalseVal;
-    if (simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q,
-                               /* AllowRefinement */ true, MaxRecurse) ==
-            FalseVal ||
-        simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q,
-                               /* AllowRefinement */ true, MaxRecurse) ==
-            FalseVal)
+    if ((CanReplaceLWithR && simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q,
+                                                    /* AllowRefinement */ true,
+                                                    MaxRecurse) == FalseVal) ||
+        (CanReplaceRWithL && simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q,
+                                                    /* AllowRefinement */ true,
+                                                    MaxRecurse) == FalseVal))
       return FalseVal;
   }
 
   return nullptr;
 }
 
 /// Try to simplify a select instruction when its condition operand is a
 /// floating-point comparison.

llvm/lib/Analysis/Loads.cpp

for (Instruction *Inst : MustNotAliasInsts)
       if (isModSet(AA.getModRefInfo(Inst, Loc)))
         return nullptr;
   }
 
   return Available;
 }
 
 bool llvm::canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
-                                     Instruction *CtxI) {
+                                     const Instruction *CtxI) {
   Type *Ty = A->getType();
   assert(Ty == B->getType() && Ty->isPointerTy() &&
          "values must have matching pointer types");
 
   // NOTE: The checks in the function are incomplete and currently miss illegal
   // cases! The current implementation is a starting point and the
   // implementation should be made stricter over time.
   if (auto *C = dyn_cast<Constant>(B)) {

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopedHashTable.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"

llvm/test/Transforms/InstSimplify/select-ptr-eq.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
 
 @y = common global [0 x i32] zeroinitializer, align 4
 
 define ptr @case1(ptr %p) {
 ; CHECK-LABEL: @case1(
-; CHECK-NEXT:    ret ptr @y
+; CHECK-NEXT:    [[C:%.*]] = icmp eq ptr [[P:%.*]], @y
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], ptr [[P]], ptr @y
+; CHECK-NEXT:    ret ptr [[RES]]
 ;
   %c = icmp eq ptr %p, @y
   %res = select i1 %c, ptr %p, ptr @y
   ret ptr %res
 }
 
 define ptr @case2(ptr %p) {
 ; CHECK-LABEL: @case2(
-; CHECK-NEXT:    ret ptr @y
+; CHECK-NEXT:    [[C:%.*]] = icmp eq ptr @y, [[P:%.*]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], ptr [[P]], ptr @y
+; CHECK-NEXT:    ret ptr [[RES]]
 ;
   %c = icmp eq ptr @y, %p
   %res = select i1 %c, ptr %p, ptr @y
   ret ptr %res
 }
 
 define ptr @case3(ptr %p) {
 ; CHECK-LABEL: @case3(
 ; CHECK-NEXT:    ret ptr [[P:%.*]]
 ;
   %c = icmp eq ptr %p, @y
   %res = select i1 %c, ptr @y, ptr %p
   ret ptr %res
 }
 
 define ptr @case4(ptr %p) {
 ; CHECK-LABEL: @case4(
 ; CHECK-NEXT:    ret ptr [[P:%.*]]
 ;
   %c = icmp eq ptr @y, %p
   %res = select i1 %c, ptr @y, ptr %p
   ret ptr %res
 }