Fix pointer comparison simplification

[joerg]

Summary

Currently, InstSimplify uses the BasicAlias notation of identifiable objects. This doesn't work correctly in a number of cases as the requirements are much stricter here. AA only cares about pointers that are deferenced, so NoAlias attributes can be considered different from global objects for this purpose. The same is not true for the pointer comparison simplification.

lib/Analysis/InlineCost.cpp

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

lib/Analysis/InstructionSimplify.cpp

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

test/Transforms/InstSimplify/compare.ll

   %Y = icmp eq i32* %X, null
   ret i1 %Y
 }
+
+@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
+}