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

On Wed, Dec 12, 2012 at 11:01:01AM -0800, Dan Gohman
wrote:
> > Is that
> > assumption violated if I explicitly cast away const and pass the
result
> > to a function with NoAlias argument?
> 
> Not immediately, no. It means that you can't access the constant
> pointer's pointee directly within the noalias argument's scope.
Access
> to that object must go through the noalias argument.
> 
> Restrict on a pointer loosely means "All accesses to my pointee(s) in
> my scope must go through me". It doesn't mean "I'm the
only pointer
> value in the  program which points to my pointee(s)"; in fact, that
> would be an unusable definition. Consequently, pointers that aren't
> used to access objects aren't constrained by restrict rules.
The original issue is that clang maps restrict on function arguments to
NoAlias and that makes compares against the address of global variables
false. Minimal test case:

@y = external global i32

define zeroext i1 @t(i32* noalias %x) nounwind uwtable readnone {
entry:
  %cmp = icmp eq i32* %x, @y
  ret i1 %cmp
}

Joerg

On Wed, Dec 12, 2012 at 1:26 PM, Joerg Sonnenberger
<joerg at britannica.bec.de> wrote:
> On Wed, Dec 12, 2012 at 11:01:01AM -0800, Dan Gohman wrote:
>> > Is that
>> > assumption violated if I explicitly cast away const and pass the
result
>> > to a function with NoAlias argument?
>>
>> Not immediately, no. It means that you can't access the constant
>> pointer's pointee directly within the noalias argument's scope.
Access
>> to that object must go through the noalias argument.
>>
>> Restrict on a pointer loosely means "All accesses to my pointee(s)
in
>> my scope must go through me". It doesn't mean "I'm
the only pointer
>> value in the  program which points to my pointee(s)"; in fact,
that
>> would be an unusable definition. Consequently, pointers that aren't
>> used to access objects aren't constrained by restrict rules.
>
> The original issue is that clang maps restrict on function arguments to
> NoAlias and that makes compares against the address of global variables
> false. Minimal test case:
>
> @y = external global i32
>
> define zeroext i1 @t(i32* noalias %x) nounwind uwtable readnone {
> entry:
>   %cmp = icmp eq i32* %x, @y
>   ret i1 %cmp
> }
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.

Dan

On Wed, Dec 12, 2012 at 01:59:55PM -0800, Dan Gohman
wrote:
> On Wed, Dec 12, 2012 at 1:26 PM, Joerg Sonnenberger
> > The original issue is that clang maps restrict on function arguments
to
> > NoAlias and that makes compares against the address of global
variables
> > false. Minimal test case:
> >
> > @y = external global i32
> >
> > define zeroext i1 @t(i32* noalias %x) nounwind uwtable readnone {
> > entry:
> >   %cmp = icmp eq i32* %x, @y
> >   ret i1 %cmp
> > }
> 
> 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.
I am just saying that the comments in BasicAliasAnalysis makes me wonder
if it has the same kind of problem.

Joerg

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);
+      }
     }
   }