llvm dev - Jan 2013 - [LLVMdev] [cfe-dev] no-alias generated as result of restrict function arguments

On Wed, Dec 12, 2012 at 01:59:55PM -0800, Dan Gohman
wrote:
> The bug here isn't in clang's use of noalias or in
BasicAliasAnalysis'
> implementation of noalias; it's in the code that's optimizing the
> icmp.
Let's come back to this. The attached patch decouples InstSimplify from
the alias analysis and provides the conservative logic for when pointers
are not equal. The only really problematic part would be InlineCost.cc,
since that could try to replace NoAlias/ByVal arguments with allocas in
the same function. For the moment, the inline cost estimation doesn't
use the SimplifyICmpInst interface and there are other parts that need
to be carefully validated before it can. It doesn't look too bad to add
an explicit argument whether interprocedural analysis is being done and
restrict the tests for that, but I am leaving this out as it is
currently unnecessary.

I am also not doing any simplification for NoAlias calls. Unlike alias
analysis, I can think of valid use cases for malloc/free/malloc
conditions where the results of the two mallocs is equal and correct
prediction of the result is desirable.

Joerg
-------------- next part --------------
Index: test/Transforms/InstSimplify/compare.ll
==================================================================---
test/Transforms/InstSimplify/compare.ll	(revision 172366)
+++ test/Transforms/InstSimplify/compare.ll	(working copy)
@@ -647,3 +647,11 @@
   %Y = icmp eq i32* %X, null
   ret i1 %Y
 }
+
+ at y = external global i32
+define zeroext i1 @external_compare(i32* noalias %x) {
+  %cmp = icmp eq i32* %x, @y
+  ret i1 %cmp
+  ; CHECK: external_compare
+  ; CHECK: ret i1 %cmp
+}
Index: lib/Analysis/InlineCost.cpp
==================================================================---
lib/Analysis/InlineCost.cpp	(revision 172366)
+++ lib/Analysis/InlineCost.cpp	(working copy)
@@ -484,6 +484,8 @@
 }
 
 bool CallAnalyzer::visitICmp(ICmpInst &I) {
+  // Do not just call SimplifyICmpInst as it can result in undefined
+  // changes when the operands involve NoAlias or ByVal arguments.
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   // First try to handle simplified comparisons.
   if (!isa<Constant>(LHS))
Index: lib/Analysis/InstructionSimplify.cpp
==================================================================---
lib/Analysis/InstructionSimplify.cpp	(revision 172366)
+++ lib/Analysis/InstructionSimplify.cpp	(working copy)
@@ -1786,59 +1786,86 @@
     }
   }
 
-  // icmp <object*>, <object*/null> - Different identified objects
have
-  // different addresses (unless null), and what's more the address of an
-  // identified local is never equal to another argument (again, barring null).
-  // Note that generalizing to the case where LHS is a global variable address
-  // or null is pointless, since if both LHS and RHS are constants then we
-  // already constant folded the compare, and if only one of them is then we
-  // moved it to RHS already.
-  Value *LHSPtr = LHS->stripPointerCasts();
-  Value *RHSPtr = RHS->stripPointerCasts();
-  if (LHSPtr == RHSPtr)
-    return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
-
-  // Be more aggressive about stripping pointer adjustments when checking a
-  // comparison of an alloca address to another object.  We can rip off all
-  // inbounds GEP operations, even if they are variable.
-  LHSPtr = LHSPtr->stripInBoundsOffsets();
-  if (llvm::isIdentifiedObject(LHSPtr)) {
-    RHSPtr = RHSPtr->stripInBoundsOffsets();
-    if (llvm::isKnownNonNull(LHSPtr) || llvm::isKnownNonNull(RHSPtr)) {
-      // If both sides are different identified objects, they aren't equal
-      // unless they're null.
-      if (LHSPtr != RHSPtr && llvm::isIdentifiedObject(RHSPtr)
&&
-          Pred == CmpInst::ICMP_EQ)
+  // icmp <object*>, <object*/null>
+  if (LHS->getType()->isPointerTy() &&
RHS->getType()->isPointerTy()) {
+    // Ignore pointer casts, they are irrevelant for (in)equality tests.
+    Value *LHSPtr = LHS->stripPointerCasts();
+    Value *RHSPtr = RHS->stripPointerCasts();
+    if (isa<ConstantPointerNull>(RHSPtr) &&
isKnownNonNull(LHSPtr)) {
+      switch (Predicate) {
+      // FIXME constant folding of remaining predicates?
+      case ICmpInst::ICMP_EQ:
         return ConstantInt::get(ITy, false);
-
-      // A local identified object (alloca or noalias call) can't equal any
-      // incoming argument, unless they're both null or they belong to
-      // different functions. The latter happens during inlining.
-      if (Instruction *LHSInst = dyn_cast<Instruction>(LHSPtr))
-        if (Argument *RHSArg = dyn_cast<Argument>(RHSPtr))
-          if (LHSInst->getParent()->getParent() == RHSArg->getParent()
&&
-              Pred == CmpInst::ICMP_EQ)
-            return ConstantInt::get(ITy, false);
+      case ICmpInst::ICMP_NE:
+        return ConstantInt::get(ITy, true);
+      }
     }
-
-    // Assume that the constant null is on the right.
-    if (llvm::isKnownNonNull(LHSPtr) &&
isa<ConstantPointerNull>(RHSPtr)) {
-      if (Pred == CmpInst::ICMP_EQ)
+    if (LHSPtr == RHSPtr) {
+      switch (Predicate) {
+      case ICmpInst::ICMP_EQ:
+      case ICmpInst::ICMP_UGE:
+      case ICmpInst::ICMP_SLE:
+        return ConstantInt::get(ITy, true);
+      case ICmpInst::ICMP_NE:
+      case ICmpInst::ICMP_UGT:
+      case ICmpInst::ICMP_SLT:
         return ConstantInt::get(ITy, false);
-      else if (Pred == CmpInst::ICMP_NE)
-        return ConstantInt::get(ITy, true);
+      default:
+        return 0;
+      }
     }
-  } else if (Argument *LHSArg = dyn_cast<Argument>(LHSPtr)) {
-    RHSPtr = RHSPtr->stripInBoundsOffsets();
-    // An alloca can't be equal to an argument unless they come from
separate
-    // functions via inlining.
-    if (AllocaInst *RHSInst = dyn_cast<AllocaInst>(RHSPtr)) {
-      if (LHSArg->getParent() == RHSInst->getParent()->getParent()) {
-        if (Pred == CmpInst::ICMP_EQ)
-          return ConstantInt::get(ITy, false);
-        else if (Pred == CmpInst::ICMP_NE)
-          return ConstantInt::get(ITy, true);
+    if (Predicate == ICmpInst::ICMP_EQ || Predicate == ICmpInst::ICMP_NE) {
+      // RHS is not a null pointer and the objects are different.
+      // Remove inbound GEPs and determine the object types.
+      LHSPtr = LHSPtr->stripInBoundsOffsets();
+      RHSPtr = RHSPtr->stripInBoundsOffsets();
+      // For allocas and arguments, remember the function they belong to.
+      const Function *lhs_func = 0;
+      const Function *rhs_func = 0;
+
+      bool lhs_alloca = isa<AllocaInst>(LHSPtr);
+      bool rhs_alloca = isa<AllocaInst>(RHSPtr);
+      bool lhs_global = isa<GlobalValue>(LHSPtr);
+      bool rhs_global = isa<GlobalValue>(RHSPtr);
+
+      bool lhs_noaliasarg = false;
+      bool rhs_noaliasarg = false;
+      bool lhs_byvalarg = false;
+      bool rhs_byvalarg = false;
+      if (const Argument *A = dyn_cast<Argument>(LHSPtr)) {
+        lhs_noaliasarg = A->hasNoAliasAttr();
+        lhs_byvalarg = A->hasByValAttr();
       }
+      if (const Argument *A = dyn_cast<Argument>(RHSPtr)) {
+        rhs_noaliasarg = A->hasNoAliasAttr();
+        rhs_byvalarg = A->hasByValAttr();
+      }
+
+      bool pred_equal = (Predicate == ICmpInst::ICMP_EQ);
+      if ((lhs_alloca && rhs_global) || (rhs_alloca &&
lhs_global))
+        return ConstantInt::get(ITy, !pred_equal);
+      // This must not be used during inline cost estimation.
+      if (lhs_alloca && (rhs_noaliasarg || rhs_byvalarg))
+        return ConstantInt::get(ITy, !pred_equal);
+      if (rhs_alloca && (lhs_noaliasarg || lhs_byvalarg))
+        return ConstantInt::get(ITy, !pred_equal);
+      if ((lhs_global && rhs_byvalarg) || (rhs_global &&
lhs_byvalarg))
+        return ConstantInt::get(ITy, !pred_equal);
+      if (lhs_alloca && rhs_alloca) {
+        // Recheck that the base objects are different and let the rest of
+        // this function deal with the case of same object, different offsets.
+        if (LHSPtr != RHSPtr)
+          return ConstantInt::get(ITy, !pred_equal);
+      }
+      if (lhs_global && rhs_global) {
+        // Recheck that the base objects are different and let the rest of
+        // this function deal with the case of same object, different offsets.
+        // Also bail out if aliases are involved.
+        bool lhs_globalalias = isa<GlobalAlias>(LHSPtr);
+        bool rhs_globalalias = isa<GlobalAlias>(RHSPtr);
+        if (!lhs_globalalias && !rhs_globalalias && LHSPtr !=
RHSPtr)
+          return ConstantInt::get(ITy, !pred_equal);
+      }
     }
   }

On Wed, Jan 16, 2013 at 12:53:55AM +0100, Joerg Sonnenberger
wrote:
> Let's come back to this. The attached patch decouples InstSimplify from
> the alias analysis and provides the conservative logic for when pointers
> are not equal.
Let's take the version with the cleanup from IRC. *sigh* Dealing with
too many copies.

Joerg
-------------- next part --------------
Index: lib/Analysis/InlineCost.cpp
==================================================================---
lib/Analysis/InlineCost.cpp	(revision 172366)
+++ lib/Analysis/InlineCost.cpp	(working copy)
@@ -484,6 +484,8 @@
 }
 
 bool CallAnalyzer::visitICmp(ICmpInst &I) {
+  // Do not just call SimplifyICmpInst as it can result in undefined
+  // changes when the operands involve NoAlias or ByVal arguments.
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   // First try to handle simplified comparisons.
   if (!isa<Constant>(LHS))
Index: lib/Analysis/InstructionSimplify.cpp
==================================================================---
lib/Analysis/InstructionSimplify.cpp	(revision 172366)
+++ lib/Analysis/InstructionSimplify.cpp	(working copy)
@@ -1786,59 +1786,69 @@
     }
   }
 
-  // icmp <object*>, <object*/null> - Different identified objects
have
-  // different addresses (unless null), and what's more the address of an
-  // identified local is never equal to another argument (again, barring null).
-  // Note that generalizing to the case where LHS is a global variable address
-  // or null is pointless, since if both LHS and RHS are constants then we
-  // already constant folded the compare, and if only one of them is then we
-  // moved it to RHS already.
-  Value *LHSPtr = LHS->stripPointerCasts();
-  Value *RHSPtr = RHS->stripPointerCasts();
-  if (LHSPtr == RHSPtr)
-    return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
+  // icmp <object*>, <object*/null>
+  if (LHS->getType()->isPointerTy() &&
RHS->getType()->isPointerTy()) {
+    // Ignore pointer casts, they are irrevelant for (in)equality tests.
+    Value *LHSPtr = LHS->stripPointerCasts();
+    Value *RHSPtr = RHS->stripPointerCasts();
+    if (LHSPtr == RHSPtr)
+      return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Predicate));
+    if (isa<ConstantPointerNull>(RHSPtr) &&
isKnownNonNull(LHSPtr)) {
+      if (ICmpInst::isEquality(Pred))
+        return ConstantInt::get(ITy, Predicate != ICmpInst::ICMP_EQ);
+    }
+    if (ICmpInst::isEquality(Pred)) {
+      // RHS is not a null pointer and the objects are different.
+      // Remove inbound GEPs and determine the object types.
+      LHSPtr = LHSPtr->stripInBoundsOffsets();
+      RHSPtr = RHSPtr->stripInBoundsOffsets();
+      // For allocas and arguments, remember the function they belong to.
+      const Function *lhs_func = 0;
+      const Function *rhs_func = 0;
 
-  // Be more aggressive about stripping pointer adjustments when checking a
-  // comparison of an alloca address to another object.  We can rip off all
-  // inbounds GEP operations, even if they are variable.
-  LHSPtr = LHSPtr->stripInBoundsOffsets();
-  if (llvm::isIdentifiedObject(LHSPtr)) {
-    RHSPtr = RHSPtr->stripInBoundsOffsets();
-    if (llvm::isKnownNonNull(LHSPtr) || llvm::isKnownNonNull(RHSPtr)) {
-      // If both sides are different identified objects, they aren't equal
-      // unless they're null.
-      if (LHSPtr != RHSPtr && llvm::isIdentifiedObject(RHSPtr)
&&
-          Pred == CmpInst::ICMP_EQ)
-        return ConstantInt::get(ITy, false);
+      bool lhs_alloca = isa<AllocaInst>(LHSPtr);
+      bool rhs_alloca = isa<AllocaInst>(RHSPtr);
+      bool lhs_global = isa<GlobalValue>(LHSPtr);
+      bool rhs_global = isa<GlobalValue>(RHSPtr);
 
-      // A local identified object (alloca or noalias call) can't equal any
-      // incoming argument, unless they're both null or they belong to
-      // different functions. The latter happens during inlining.
-      if (Instruction *LHSInst = dyn_cast<Instruction>(LHSPtr))
-        if (Argument *RHSArg = dyn_cast<Argument>(RHSPtr))
-          if (LHSInst->getParent()->getParent() == RHSArg->getParent()
&&
-              Pred == CmpInst::ICMP_EQ)
-            return ConstantInt::get(ITy, false);
-    }
+      bool lhs_noaliasarg = false;
+      bool rhs_noaliasarg = false;
+      bool lhs_byvalarg = false;
+      bool rhs_byvalarg = false;
+      if (const Argument *A = dyn_cast<Argument>(LHSPtr)) {
+        lhs_noaliasarg = A->hasNoAliasAttr();
+        lhs_byvalarg = A->hasByValAttr();
+      }
+      if (const Argument *A = dyn_cast<Argument>(RHSPtr)) {
+        rhs_noaliasarg = A->hasNoAliasAttr();
+        rhs_byvalarg = A->hasByValAttr();
+      }
 
-    // Assume that the constant null is on the right.
-    if (llvm::isKnownNonNull(LHSPtr) &&
isa<ConstantPointerNull>(RHSPtr)) {
-      if (Pred == CmpInst::ICMP_EQ)
-        return ConstantInt::get(ITy, false);
-      else if (Pred == CmpInst::ICMP_NE)
-        return ConstantInt::get(ITy, true);
-    }
-  } else if (Argument *LHSArg = dyn_cast<Argument>(LHSPtr)) {
-    RHSPtr = RHSPtr->stripInBoundsOffsets();
-    // An alloca can't be equal to an argument unless they come from
separate
-    // functions via inlining.
-    if (AllocaInst *RHSInst = dyn_cast<AllocaInst>(RHSPtr)) {
-      if (LHSArg->getParent() == RHSInst->getParent()->getParent()) {
-        if (Pred == CmpInst::ICMP_EQ)
-          return ConstantInt::get(ITy, false);
-        else if (Pred == CmpInst::ICMP_NE)
-          return ConstantInt::get(ITy, true);
+      bool pred_equal = (Predicate == ICmpInst::ICMP_EQ);
+      if ((lhs_alloca && rhs_global) || (rhs_alloca &&
lhs_global))
+        return ConstantInt::get(ITy, !pred_equal);
+      // This must not be used during inline cost estimation.
+      if (lhs_alloca && (rhs_noaliasarg || rhs_byvalarg))
+        return ConstantInt::get(ITy, !pred_equal);
+      if (rhs_alloca && (lhs_noaliasarg || lhs_byvalarg))
+        return ConstantInt::get(ITy, !pred_equal);
+      if ((lhs_global && rhs_byvalarg) || (rhs_global &&
lhs_byvalarg))
+        return ConstantInt::get(ITy, !pred_equal);
+      if (lhs_alloca && rhs_alloca) {
+        // Recheck that the base objects are different and let the rest of
+        // this function deal with the case of same object, different offsets.
+        if (LHSPtr != RHSPtr)
+          return ConstantInt::get(ITy, !pred_equal);
       }
+      if (lhs_global && rhs_global) {
+        // Recheck that the base objects are different and let the rest of
+        // this function deal with the case of same object, different offsets.
+        // Also bail out if aliases are involved.
+        bool lhs_globalalias = isa<GlobalAlias>(LHSPtr);
+        bool rhs_globalalias = isa<GlobalAlias>(RHSPtr);
+        if (!lhs_globalalias && !rhs_globalalias && LHSPtr !=
RHSPtr)
+          return ConstantInt::get(ITy, !pred_equal);
+      }
     }
   }
 
Index: test/Transforms/InstSimplify/compare.ll
==================================================================---
test/Transforms/InstSimplify/compare.ll	(revision 172366)
+++ test/Transforms/InstSimplify/compare.ll	(working copy)
@@ -647,3 +647,11 @@
   %Y = icmp eq i32* %X, null
   ret i1 %Y
 }
+
+ at y = external global i32
+define zeroext i1 @external_compare(i32* noalias %x) {
+  %cmp = icmp eq i32* %x, @y
+  ret i1 %cmp
+  ; CHECK: external_compare
+  ; CHECK: ret i1 %cmp
+}

On Wed, Jan 16, 2013 at 2:39 AM, Joerg Sonnenberger
<joerg at britannica.bec.de> wrote:
> On Wed, Jan 16, 2013 at 12:53:55AM +0100, Joerg Sonnenberger wrote:
>> Let's come back to this. The attached patch decouples InstSimplify
from
>> the alias analysis and provides the conservative logic for when
pointers
>> are not equal.
>
> Let's take the version with the cleanup from IRC. *sigh* Dealing with
> too many copies.
One of InstructionSimplify's strengths is that it is simple. Having
constraints where its users have to know which calls are safe in which
contexts would make it tricky. Having a flag you pass in to tell it
what kind of context you're calling it from would complicate it. And,
we've had numerous (on and off-list) emails just to understand the
problem to the extent that we do now, and I'm still not fully
convinced we understand it fully.

How important is this optimization? Do you have real-world code where
it matters?

Intuitively, it seems that the kind of pointer comparisons you're
aiming at would be uncommon. Code authors can avoid them for the same
reason that you think the compiler can eliminate them (except that a
code author typically doesn't have to worry about their own code being
pathological, while the optimizer does). I'm aware that code can often
look pretty surprising after macro expansion and inlining, but anyone
choosing to add restrict to their pointers is obliged to be fairly
careful about how such pointers are used.

Dan