Index: llvm/include/llvm/IR/Instructions.h =================================================================== --- llvm/include/llvm/IR/Instructions.h +++ llvm/include/llvm/IR/Instructions.h @@ -33,6 +33,7 @@ #include "llvm/IR/User.h" #include "llvm/Support/AtomicOrdering.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/IR/Operator.h" #include #include #include @@ -1149,6 +1150,13 @@ static bool classof(const Value *V) { return isa(V) && classof(cast(V)); } + + /// Determine if two GEPs have different offsets, if possible. + /// + /// It is difficult to determine whether two GEPs point to the same offset. + /// However, it is possible to determine whether two GEPs are not equal + /// when the indices of the two GEPs are the same. + bool hasDifferOffset(const DataLayout &DL, const GEPOperator &GEP) const; }; template <> Index: llvm/include/llvm/IR/Operator.h =================================================================== --- llvm/include/llvm/IR/Operator.h +++ llvm/include/llvm/IR/Operator.h @@ -512,6 +512,13 @@ bool collectOffset(const DataLayout &DL, unsigned BitWidth, MapVector &VariableOffsets, APInt &ConstantOffset) const; + + /// Determine two GEPs have different offset if possible. + /// + /// In general, the offset of two GEPs cannot be calculated perfectly + /// because of past-the-end. However, in certain cases, the same and + /// different can be determined. + bool hasDifferOffset(const DataLayout &DL, const GEPOperator &GEP) const; }; class PtrToIntOperator Index: llvm/lib/Analysis/InstructionSimplify.cpp =================================================================== --- llvm/lib/Analysis/InstructionSimplify.cpp +++ llvm/lib/Analysis/InstructionSimplify.cpp @@ -3757,12 +3757,25 @@ if (Value *V = simplifyICmpWithConstant(Pred, LHS, RHS, Q.IIQ)) return V; - // If both operands have range metadata, use the metadata - // to simplify the comparison. if (isa(RHS) && isa(LHS)) { auto RHS_Instr = cast(RHS); auto LHS_Instr = cast(LHS); + // GetElementPtrInst specific logic + if (ICmpInst::isEquality(Pred) && isa(LHS) && + isa(RHS)) { + DataLayout DL(LHS_Instr->getModule()); + const auto GEP1 = dyn_cast(LHS); + const auto GEP2 = dyn_cast(RHS); + + if (haveNonOverlappingStorage(GEP1->getPointerOperand(), + GEP2->getPointerOperand())) + if (GEP1->hasDifferOffset(DL, *GEP2)) + return Pred == ICmpInst::ICMP_NE ? getTrue(ITy) : getFalse(ITy); + } + + // If both operands have range metadata, use the metadata + // to simplify the comparison. if (Q.IIQ.getMetadata(RHS_Instr, LLVMContext::MD_range) && Q.IIQ.getMetadata(LHS_Instr, LLVMContext::MD_range)) { auto RHS_CR = getConstantRangeFromMetadata( Index: llvm/lib/IR/ConstantFold.cpp =================================================================== --- llvm/lib/IR/ConstantFold.cpp +++ llvm/lib/IR/ConstantFold.cpp @@ -1544,15 +1544,12 @@ // By far the most common case to handle is when the base pointers are // obviously to the same global. const Constant *CE2Op0 = cast(CE2GEP->getPointerOperand()); - if (isa(CE1Op0) && isa(CE2Op0)) { - // Don't know relative ordering, but check for inequality. - if (CE1Op0 != CE2Op0) { - if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices()) - return areGlobalsPotentiallyEqual(cast(CE1Op0), - cast(CE2Op0)); - return ICmpInst::BAD_ICMP_PREDICATE; - } - } + DataLayout DL(dyn_cast(CE1Op0)->getParent()); + if (CE1GEP->hasDifferOffset(DL, *CE2GEP)) + return areGlobalsPotentiallyEqual(cast(CE1Op0), + cast(CE2Op0)); + + return ICmpInst::BAD_ICMP_PREDICATE; } break; } Index: llvm/lib/IR/Instructions.cpp =================================================================== --- llvm/lib/IR/Instructions.cpp +++ llvm/lib/IR/Instructions.cpp @@ -1974,6 +1974,12 @@ ConstantOffset); } +bool GetElementPtrInst::hasDifferOffset(const DataLayout &DL, + const GEPOperator &GEP) const { + // Delegate to the generic GEPOperator implementation. + return cast(this)->hasDifferOffset(DL, GEP); +} + //===----------------------------------------------------------------------===// // ExtractElementInst Implementation //===----------------------------------------------------------------------===// Index: llvm/lib/IR/Operator.cpp =================================================================== --- llvm/lib/IR/Operator.cpp +++ llvm/lib/IR/Operator.cpp @@ -232,6 +232,29 @@ return true; } +bool GEPOperator::hasDifferOffset(const DataLayout &DL, + const GEPOperator &GEP) const { + auto GEP1ptr = getPointerOperand(); + auto GEP2ptr = GEP.getPointerOperand(); + + if (GEP1ptr != GEP2ptr) { + if ((hasIndices() && hasAllConstantIndices()) && + (GEP.hasIndices() && GEP.hasAllConstantIndices())) { + if (hasAllZeroIndices() && GEP.hasAllZeroIndices()) + return true; + + APInt GEP1Offset(DL.getIndexTypeSizeInBits(getType()), 0); + APInt GEP2Offset(DL.getIndexTypeSizeInBits(GEP.getType()), 0); + if (accumulateConstantOffset(DL, GEP1Offset) && + GEP.accumulateConstantOffset(DL, GEP2Offset) && + GEP1Offset == GEP2Offset) + return true; + } + } + + return false; +} + void FastMathFlags::print(raw_ostream &O) const { if (all()) O << " fast"; Index: llvm/test/Transforms/InstSimplify/cmp-alloca-offsets.ll =================================================================== --- llvm/test/Transforms/InstSimplify/cmp-alloca-offsets.ll +++ llvm/test/Transforms/InstSimplify/cmp-alloca-offsets.ll @@ -40,15 +40,9 @@ ret i1 %res } -; FIXME: Can't be equal define i1 @positive_non_equal_end() { ; CHECK-LABEL: @positive_non_equal_end( -; CHECK-NEXT: [[A:%.*]] = alloca i8, i32 4, align 1 -; CHECK-NEXT: [[B:%.*]] = alloca i8, i32 4, align 1 -; CHECK-NEXT: [[A_OFF:%.*]] = getelementptr i8, ptr [[A]], i64 4 -; CHECK-NEXT: [[B_OFF:%.*]] = getelementptr i8, ptr [[B]], i64 4 -; CHECK-NEXT: [[RES:%.*]] = icmp ne ptr [[A_OFF]], [[B_OFF]] -; CHECK-NEXT: ret i1 [[RES]] +; CHECK-NEXT: ret i1 true ; %a = alloca i8, i32 4 %b = alloca i8, i32 4 Index: llvm/test/Transforms/InstSimplify/compare.ll =================================================================== --- llvm/test/Transforms/InstSimplify/compare.ll +++ llvm/test/Transforms/InstSimplify/compare.ll @@ -2778,10 +2778,9 @@ ret i1 %res } -; TODO: Never equal define i1 @globals_offset_inequal() { ; CHECK-LABEL: @globals_offset_inequal( -; CHECK-NEXT: ret i1 icmp ne (ptr getelementptr (i8, ptr @A, i32 1), ptr getelementptr (i8, ptr @B, i32 1)) +; CHECK-NEXT: ret i1 true ; %a.off = getelementptr i8, ptr @A, i32 1 %b.off = getelementptr i8, ptr @B, i32 1 Index: llvm/test/Transforms/InstSimplify/past-the-end.ll =================================================================== --- llvm/test/Transforms/InstSimplify/past-the-end.ll +++ llvm/test/Transforms/InstSimplify/past-the-end.ll @@ -17,17 +17,14 @@ ret i1 %t } -; Comparing past-the-end addresses of two distinct globals. Never equal. - define zeroext i1 @both_past_the_end() { ; CHECK-LABEL: @both_past_the_end( -; CHECK: ret i1 icmp eq (ptr getelementptr inbounds (i32, ptr @opte_a, i32 1), ptr getelementptr inbounds (i32, ptr @opte_b, i32 1)) +; CHECK: ret i1 false ; %x = getelementptr i32, ptr @opte_a, i32 1 %y = getelementptr i32, ptr @opte_b, i32 1 %t = icmp eq ptr %x, %y ret i1 %t - ; TODO: refine this } ; Comparing past-the-end addresses of one global to the base address @@ -58,12 +55,7 @@ define zeroext i1 @both_past_the_end_alloca() { ; CHECK-LABEL: @both_past_the_end_alloca( -; CHECK: [[M:%.*]] = alloca i32 -; CHECK-NEXT: [[N:%.*]] = alloca i32 -; CHECK-NEXT: [[X:%.*]] = getelementptr i32, ptr [[M]], i32 1 -; CHECK-NEXT: [[Y:%.*]] = getelementptr i32, ptr [[N]], i32 1 -; CHECK-NEXT: [[T:%.*]] = icmp eq ptr [[X]], [[Y]] -; CHECK-NEXT: ret i1 [[T]] +; CHECK-NEXT: ret i1 false ; %m = alloca i32 %n = alloca i32 @@ -71,7 +63,6 @@ %y = getelementptr i32, ptr %n, i32 1 %t = icmp eq ptr %x, %y ret i1 %t - ; TODO: refine this } ; Comparing past-the-end addresses of one alloca to the base address