IR: Fold away compares between GV GEPs and GVs

[majnemer]

Summary

A GEP of a non-weak global variable will not be equivalent to another
non-weak global variable or a GEP of such a variable.

[nlewycky]

lib/IR/ConstantFold.cpp

1339 ↗

(On Diff #10712)

(No action required:) I realize this is copied from elsewhere, but I don't see why we can't follow non-weak aliases as long as they point to definitions.

1538 ↗

(On Diff #10712)

// Don't know relative ordering, but check for inequality.

[majnemer]

Closed by commit rL212360 (authored by @majnemer).

llvm/trunk/lib/IR/ConstantFold.cpp

default:
       break;
     }
   }
   // There are MANY other foldings that we could perform here.  They will
   // probably be added on demand, as they seem needed.
   return FCmpInst::BAD_FCMP_PREDICATE;
 }
 
+static ICmpInst::Predicate areGlobalsPotentiallyEqual(const GlobalValue *GV1,
+                                                      const GlobalValue *GV2) {
+  // Don't try to decide equality of aliases.
+  if (!isa<GlobalAlias>(GV1) && !isa<GlobalAlias>(GV2))
+    if (!GV1->hasExternalWeakLinkage() || !GV2->hasExternalWeakLinkage())
+      return ICmpInst::ICMP_NE;
+  return ICmpInst::BAD_ICMP_PREDICATE;
+}
+
 /// evaluateICmpRelation - This function determines if there is anything we can
 /// decide about the two constants provided.  This doesn't need to handle simple
 /// things like integer comparisons, but should instead handle ConstantExprs
 /// and GlobalValues.  If we can determine that the two constants have a
 /// particular relation to each other, we should return the corresponding ICmp
 /// predicate, otherwise return ICmpInst::BAD_ICMP_PREDICATE.
 ///
 /// To simplify this code we canonicalize the relation so that the first
if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
         return ICmpInst::getSwappedPredicate(SwappedRelation);
       return ICmpInst::BAD_ICMP_PREDICATE;
     }
 
     // Now we know that the RHS is a GlobalValue, BlockAddress or simple
     // constant (which, since the types must match, means that it's a
     // ConstantPointerNull).
     if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) {
-      // Don't try to decide equality of aliases.
-      if (!isa<GlobalAlias>(GV) && !isa<GlobalAlias>(GV2))
-        if (!GV->hasExternalWeakLinkage() || !GV2->hasExternalWeakLinkage())
-          return ICmpInst::ICMP_NE;
+      return areGlobalsPotentiallyEqual(GV, GV2);
     } else if (isa<BlockAddress>(V2)) {
       return ICmpInst::ICMP_NE; // Globals never equal labels.
     } else {
       assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
       // GlobalVals can never be null unless they have external weak linkage.
       // We don't try to evaluate aliases here.
       if (!GV->hasExternalWeakLinkage() && !isa<GlobalAlias>(GV))
         return ICmpInst::ICMP_NE;
case Instruction::SExt:
         if (CE1->getOpcode() == Instruction::ZExt) isSigned = false;
         if (CE1->getOpcode() == Instruction::SExt) isSigned = true;
         return evaluateICmpRelation(CE1Op0,
                                     Constant::getNullValue(CE1Op0->getType()), 
                                     isSigned);
       }
       break;
 
-    case Instruction::GetElementPtr:
+    case Instruction::GetElementPtr: {
+      GEPOperator *CE1GEP = cast<GEPOperator>(CE1);
       // Ok, since this is a getelementptr, we know that the constant has a
       // pointer type.  Check the various cases.
       if (isa<ConstantPointerNull>(V2)) {
         // If we are comparing a GEP to a null pointer, check to see if the base
         // of the GEP equals the null pointer.
         if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
           if (GV->hasExternalWeakLinkage())
             // Weak linkage GVals could be zero or not. We're comparing that
case Instruction::GetElementPtr: {
             // different.  Because the types must match, the getelementptr could
             // only have at most one index, and because we fold getelementptr's
             // with a single zero index, it must be nonzero.
             assert(CE1->getNumOperands() == 2 &&
                    !CE1->getOperand(1)->isNullValue() &&
                    "Surprising getelementptr!");
             return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
           } else {
-            // If they are different globals, we don't know what the value is.
+            if (CE1GEP->hasAllZeroIndices())
+              return areGlobalsPotentiallyEqual(GV, GV2);
             return ICmpInst::BAD_ICMP_PREDICATE;
           }
         }
       } else {
         ConstantExpr *CE2 = cast<ConstantExpr>(V2);
         Constant *CE2Op0 = CE2->getOperand(0);
 
         // There are MANY other foldings that we could perform here.  They will
         // probably be added on demand, as they seem needed.
         switch (CE2->getOpcode()) {
         default: break;
         case Instruction::GetElementPtr:
           // By far the most common case to handle is when the base pointers are
           // obviously to the same global.
           if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
-            if (CE1Op0 != CE2Op0) // Don't know relative ordering.
+            // Don't know relative ordering, but check for inequality.
+            if (CE1Op0 != CE2Op0) {
+              GEPOperator *CE2GEP = cast<GEPOperator>(CE2);
+              if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices())
+                return areGlobalsPotentiallyEqual(cast<GlobalValue>(CE1Op0),
+                                                  cast<GlobalValue>(CE2Op0));
               return ICmpInst::BAD_ICMP_PREDICATE;
+            }
             // Ok, we know that both getelementptr instructions are based on the
             // same global.  From this, we can precisely determine the relative
             // ordering of the resultant pointers.
             unsigned i = 1;
 
             // The logic below assumes that the result of the comparison
             // can be determined by finding the first index that differs.
             // This doesn't work if there is over-indexing in any
case Instruction::GetElementPtr: {
                   return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
                 else
                   return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
               }
             return ICmpInst::ICMP_EQ;
           }
         }
       }
+    }
     default:
       break;
     }
   }
 
   return ICmpInst::BAD_ICMP_PREDICATE;
 }
 

llvm/trunk/test/Other/constant-fold-gep.ll

 
 define i8* @same_addrspace() nounwind noinline {
 ; OPT: same_addrspace
   %p = getelementptr inbounds i8* bitcast ([4 x i8] * @p0 to i8*), i32 2
   ret i8* %p
 ; OPT: ret i8* getelementptr inbounds ([4 x i8]* @p0, i32 0, i32 2)
 }
 
+@gv1 = internal global i32 1
+@gv2 = internal global [1 x i32] [ i32 2 ]
+@gv3 = internal global [1 x i32] [ i32 2 ]
+
+; Handled by TI-independent constant folder
+define i1 @gv_gep_vs_gv() {
+  ret i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @gv2, i32 0, i32 0), i32* @gv1)
+}
+; PLAIN: gv_gep_vs_gv
+; PLAIN: ret i1 false
+
+define i1 @gv_gep_vs_gv_gep() {
+  ret i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @gv2, i32 0, i32 0), i32* getelementptr inbounds ([1 x i32]* @gv3, i32 0, i32 0))
+}
+; PLAIN: gv_gep_vs_gv_gep
+; PLAIN: ret i1 false
+
 ; CHECK: attributes #0 = { nounwind }

llvm/trunk/test/Transforms/InstCombine/2010-03-03-ExtElim.ll

 }
 
 @d = common global i32 0, align 4
 @a = common global [1 x i32] zeroinitializer, align 4
 
 define i1 @PR16462_1() nounwind {
 ; CHECK-LABEL: @PR16462_1(
   ret i1 icmp sgt (i32 sext (i16 trunc (i32 select (i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @a, i32 0, i32 0), i32* @d), i32 0, i32 1) to i16) to i32), i32 65535)
-; CHECK: ret i1 icmp sgt (i32 sext (i16 trunc (i32 select (i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @a, i32 0, i32 0), i32* @d), i32 0, i32 1) to i16) to i32), i32 65535)
+; CHECK: ret i1 false
 }
 
 define i1 @PR16462_2() nounwind {
 ; CHECK-LABEL: @PR16462_2(
   ret i1 icmp sgt (i32 sext (i16 trunc (i32 select (i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @a, i32 0, i32 0), i32* @d), i32 0, i32 1) to i16) to i32), i32 42)
-; CHECK: ret i1 icmp sgt (i16 trunc (i32 select (i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @a, i32 0, i32 0), i32* @d), i32 0, i32 1) to i16), i16 42)
+; CHECK: ret i1 false
 }

llvm/trunk/test/Transforms/InstCombine/pr20079.ll

 ; RUN: opt -S -instcombine < %s | FileCheck %s
 @b = internal global [1 x i32] zeroinitializer, align 4
 @c = internal global i32 0, align 4
 
 ; CHECK-LABEL: @fn1
-; CHECK: [[ADD:%.*]] = add i32 %a, -1
-; CHECK-NEXT: [[AND:%.*]] = and i32 [[ADD]], sub (i32 0, i32 zext (i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @b, i64 0, i64 0), i32* @c) to i32))
-; CHECK-NEXT: ret i32 [[AND]]
+; CHECK-NEXT: ret i32 0
 define i32 @fn1(i32 %a) {
-  %xor = add i32 %a, -1
-  %mul = mul nsw i32 %xor, zext (i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @b, i64 0, i64 0), i32* @c) to i32)
-  ret i32 %mul
+  ret i32 0
 }

llvm/trunk/test/Transforms/LoopVectorize/if-conversion.ll

entry:
   br label %for.body
 
 for.body:
   %inc3 = phi i32 [ 0, %entry ], [ %inc, %cond.end ]
   %or2 = phi i32 [ 0, %entry ], [ %or, %cond.end ]
   br i1 icmp eq (i32** getelementptr inbounds ([1 x i32*]* @a, i64 0, i64 0), i32** @c), label %cond.false, label %cond.end
 
 cond.false:
-  %cond.1 = or i32 %inc3, sdiv (i32 1, i32 zext (i1 icmp eq (i32** getelementptr inbounds ([1 x i32*]* @a, i64 0, i64 0), i32** @c) to i32))
+  %cond.1 = or i32 %inc3, sdiv (i32 1, i32 zext (i1 icmp eq (i32** getelementptr inbounds ([1 x i32*]* @a, i64 0, i64 1), i32** @c) to i32))
   br label %cond.end
 
 cond.end:
   %cond = phi i32 [ %cond.1, %cond.false ], [ %inc3, %for.body ]
   %or = or i32 %or2, %cond
   %inc = add nsw i32 %inc3, 1
   %cmp = icmp slt i32 %inc, 128
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret i32 %or
 }