[InstSimplify] Fold ne/eq comparison of a pointer produced by a noalias function

[xbolva00]

Summary

Example:

declare noalias i8* @malloc(i64)

define i1 @compare_noalias(i64 %x, i8* %y) {

%m = call i8* @malloc(i64 %x)
%r = icmp eq i8* %m, %y
ret i1 %r

}

In this case %r must be false because @malloc has the 'noalias' attribute.

Fixes PR38956

[lebedev.ri]

Are there tests with comparisons with nullptr? (Also mind the nullptr is valid thingy)

test/Transforms/InstSimplify/icmp-noalias-pointers.ll

22–23

Just return i1? I don't think we care about anything else other than the i1.

[xbolva00]

Yes, I will add more tests. Suggestions welcome.

test/Transforms/InstSimplify/icmp-noalias-pointers.ll

22–23

Ok, I will change it.

[hfinkel]

Unfortunately, I don't think that we can do this. noalias semantics only provide information about the overlap of memory accesses using the resulting pointers, in the context of other necessary constraints, and does not strongly constrain the pointer values. For example, it might be that:

int *x = malloc(n);
free(x);
int *y = malloc(n);
if (y == x) // should we always fold this to false?
  printf("malloc reused memory");

Also, what happens if the result is null, and you're comparing to a value which also happens to be null?

[xbolva00]

Ok.. so maybe

• disable this fold when comparing noalias ptr with null
• disable also when cmp' rhs and lhs are both noalias ptrs

?

Any further caveats?

[xbolva00]

int f(int n) {

int *x = (int *)malloc(n);
free(x);
int *y =  (int *)malloc(n);
return (y == x) ;

}

This has been already folded to true even before this patch.

[hfinkel]

disable this fold when comparing noalias ptr with null

But it's not just comparing to a nullptr constant, it's also comparing to another SSA value that, dynamically, is null.

[hfinkel]

In D52164#1237112, @xbolva00 wrote:

int f(int n) {

int *x = (int *)malloc(n);
free(x);
int *y =  (int *)malloc(n);
return (y == x) ;

}

This has been already folded to true even before this patch.

You need to look at how this folding happens? Does it still happen if you actually use the allocation for something? We fold unused allocations away, as I recall.

[xbolva00]

Yes, we only fold if it is not used. :)

[xbolva00]

In D52164#1237188, @hfinkel wrote:

disable this fold when comparing noalias ptr with null

But it's not just comparing to a nullptr constant, it's also comparing to another SSA value that, dynamically, is null.

Yeah.

But like the original idea was, we could handle comparison of noalias ptr to ptr pointing to global vars/functions, no?

lib/Analysis/InstructionSimplify.cpp

 }
 
 /// For a boolean type or a vector of boolean type, return true or a vector
 /// with every element true.
 static Constant *getTrue(Type *Ty) {
   return ConstantInt::getTrue(Ty);
 }
 
+static Type *GetCompareTy(Value *Op) {
+  return CmpInst::makeCmpResultType(Op->getType());
+}
+
 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
 static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
                           Value *RHS) {
   CmpInst *Cmp = dyn_cast<CmpInst>(V);
   if (!Cmp)
     return false;
   CmpInst::Predicate CPred = Cmp->getPredicate();
   Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
   // then it obviously dominates all phi nodes.
   if (I->getParent() == &I->getFunction()->getEntryBlock() &&
       !isa<InvokeInst>(I))
     return true;
 
   return false;
 }
 
+// ne/eq comparison of a pointer produced by a noalias function can be folded to
+// a constant true/false
+static Value *simplifyICmpWithNoAliasPointers(unsigned Predicate, Value *LHS,
+                                              Value *RHS) {
+  Value *HS[] = {LHS, RHS};
+  for (int i = 0; i < 2; ++i) {
+    if (CallInst *Call = dyn_cast<CallInst>(HS[i])) {
+      Function *Fn = Call->getCalledFunction();
+      if (!Fn || !Fn->returnDoesNotAlias())
+        return nullptr;
+    }
+  }
+
+  Type *ITy = GetCompareTy(LHS);
+  if (Predicate == ICmpInst::ICMP_EQ)
+    return getFalse(ITy);
+  else if (Predicate == ICmpInst::ICMP_NE)
+    return getTrue(ITy);
+
+  return nullptr;
+}
+
 /// Simplify "A op (B op' C)" by distributing op over op', turning it into
 /// "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
 /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
 /// Returns the simplified value, or null if no simplification was performed.
 static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
                           Instruction::BinaryOps OpcodeToExpand,
                           const SimplifyQuery &Q, unsigned MaxRecurse) {
static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
 
   return nullptr;
 }
 
 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifyXorInst(Op0, Op1, Q, RecursionLimit);
 }
 
-
-static Type *GetCompareTy(Value *Op) {
-  return CmpInst::makeCmpResultType(Op->getType());
-}
-
 /// Rummage around inside V looking for something equivalent to the comparison
 /// "LHS Pred RHS". Return such a value if found, otherwise return null.
 /// Helper function for analyzing max/min idioms.
 static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred,
                                          Value *LHS, Value *RHS) {
   SelectInst *SI = dyn_cast<SelectInst>(V);
   if (!SI)
     return nullptr;
if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
       return V;
 
   // If the comparison is with the result of a phi instruction, check whether
   // doing the compare with each incoming phi value yields a common result.
   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
       return V;
 
+  if (Value *V = simplifyICmpWithNoAliasPointers(Pred, LHS, RHS))
+    return V;
+
   return nullptr;
 }
 
 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                               const SimplifyQuery &Q) {
   return ::SimplifyICmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
 }
 

test/Transforms/InstSimplify/icmp-noalias-pointers.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s
+
+@a = global [32 x i8] c"string\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00", align 16
+@b = common global [32 x i8] zeroinitializer, align 16
+
+declare noalias i8* @realloc(i8* nocapture, i64) local_unnamed_addr
+declare i8* @custom_aliasing_alloc(i64) local_unnamed_addr
+declare noalias i8* @__strdup(i8* nocapture readonly) local_unnamed_addr
+declare noalias i8* @calloc(i64, i64) local_unnamed_addr
+declare noalias i8* @malloc(i64) local_unnamed_addr
+
+declare i32 @foo()
+
+define i1 @noalias_compare_fn_ptr_eq() {
+; CHECK-LABEL: @noalias_compare_fn_ptr_eq(
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp eq i8* %call, bitcast (i32 ()* @foo to i8*)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_fn_ptr_ne() {
+; CHECK-LABEL: @noalias_compare_fn_ptr_ne(
+; CHECK-NEXT:    ret i1 true
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ne i8* %call, bitcast (i32 ()* @foo to i8*)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_null_eq() {
+; CHECK-LABEL: @noalias_compare_null_eq(
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp eq i8* %call, null
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_null_ne() {
+; CHECK-LABEL: @noalias_compare_null_ne(
+; CHECK-NEXT:    ret i1 true
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ne i8* %call, null
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_arg_eq(i8* readnone %r) {
+; CHECK-LABEL: @noalias_compare_arg_eq(
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp eq i8* %call, %r
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_arg_ne(i8* readnone %r) {
+; CHECK-LABEL: @noalias_compare_arg_ne(
+; CHECK-NEXT:    ret i1 true
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ne i8* %call, %r
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_const_str_eq_malloc() {
+; CHECK-LABEL: @noalias_compare_const_str_eq_malloc(
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp eq i8* %call, getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_const_str_eq_calloc() {
+; CHECK-LABEL: @noalias_compare_const_str_eq_calloc(
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call noalias i8* @calloc(i64 1, i64 32)
+  %cmp = icmp eq i8* %call, getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_const_str_eq_realloc(i8* nocapture %r) {
+; CHECK-LABEL: @noalias_compare_const_str_eq_realloc(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @realloc(i8* [[R:%.*]], i64 32)
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call i8* @realloc(i8* %r, i64 32)
+  %cmp = icmp eq i8* %call, getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_const_str_eq_strdup(i8* nocapture readonly %s) {
+; CHECK-LABEL: @noalias_compare_const_str_eq_strdup(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias i8* @__strdup(i8* [[S:%.*]])
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call noalias i8* @__strdup(i8* %s)
+  %cmp = icmp eq i8* %call, getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_const_str_ne() {
+; CHECK-LABEL: @noalias_compare_const_str_ne(
+; CHECK-NEXT:    ret i1 true
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ne i8* %call, getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_const_str2_eq() {
+; CHECK-LABEL: @noalias_compare_const_str2_eq(
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp eq i8* %call, getelementptr inbounds ([32 x i8], [32 x i8]* @b, i64 0, i64 0)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_const_str2_ne() {
+; CHECK-LABEL: @noalias_compare_const_str2_ne(
+; CHECK-NEXT:    ret i1 true
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ne i8* %call, getelementptr inbounds ([32 x i8], [32 x i8]* @b, i64 0, i64 0)
+  ret i1 %cmp
+}
+
+; Negative tests
+define i1 @unknown_alias_compare_fn_ptr_eq() {
+; CHECK-LABEL: @unknown_alias_compare_fn_ptr_eq(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @custom_aliasing_alloc(i64 32)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8* [[CALL]], bitcast (i32 ()* @foo to i8*)
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %call = tail call i8* @custom_aliasing_alloc(i64 32)
+  %cmp = icmp eq i8* %call, bitcast (i32 ()* @foo to i8*)
+  ret i1 %cmp
+}
+
+define i1 @unknown_alias_compare_fn_ptr_ne() {
+; CHECK-LABEL: @unknown_alias_compare_fn_ptr_ne(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @custom_aliasing_alloc(i64 32)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8* [[CALL]], bitcast (i32 ()* @foo to i8*)
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %call = tail call i8* @custom_aliasing_alloc(i64 32)
+  %cmp = icmp ne i8* %call, bitcast (i32 ()* @foo to i8*)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_fn_ptr_gt() {
+; CHECK-LABEL: @noalias_compare_fn_ptr_gt(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias i8* @malloc(i64 32)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8* [[CALL]], bitcast (i32 ()* @foo to i8*)
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ugt i8* %call, bitcast (i32 ()* @foo to i8*)
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_fn_ptr_lt() {
+; CHECK-LABEL: @noalias_compare_fn_ptr_lt(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias i8* @malloc(i64 32)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8* [[CALL]], bitcast (i32 ()* @foo to i8*)
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ult i8* %call, bitcast (i32 ()* @foo to i8*)
+  ret i1 %cmp
+}
+
+
+define i1 @noalias_compare_null_gt() {
+; CHECK-LABEL: @noalias_compare_null_gt(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias i8* @malloc(i64 32)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8* [[CALL]], null
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ugt i8* %call, null
+  ret i1 %cmp
+}
+
+define i1 @noalias_compare_noalias_compare_null_gt_lt() {
+; CHECK-LABEL: @noalias_compare_noalias_compare_null_gt_lt(
+; CHECK-NEXT:    ret i1 false
+;
+  %call = tail call noalias i8* @malloc(i64 32)
+  %cmp = icmp ult i8* %call, null
+  ret i1 %cmp
+}