[InstCombine] Look through more casts when folding memchr and memcmp

[msebor]

Summary

The memchr and memcmp folders fail for the results of pointer addition involving fractional offsets into constants of types other than i8, such as in

const int a[] = { 0x01010101, 0x02020202 };

void* f (void)
{
  return memchr((const char*)a + 1, 1, 7);
}

and similar examples involving structs and unions. This is due to what seems like an overly restrictive check in the getConstantDataArrayInfo that keeps the function from "looking through [all] bitcast instructions and geps" despite the comment documenting this intent.

In conjunction with the recent enhancement to let all libcall folders work with subobjects of constants of arbitrary types (D125114), this change removes the limitation above, bringing the memchr and memcmp folders up to par with GCC. Tested on by running make check-all on x86_64-linux.

(The code in getConstantDataArrayInfo could stand to be simplified by letting the function take a DataLayout argument. I stopped short of making that change in this patch to minimize the extent of the changes.)

[efriedma]

llvm/lib/Analysis/ValueTracking.cpp

4196

Maybe it makes sense to just drop the dyn_cast<GlobalVariable> here?

4287

Not sure I understand this change; why does it matter if the slice is zero-length here?

[msebor]

llvm/lib/Analysis/ValueTracking.cpp

4196

This is what I meant by the simplification opportunity (I think we discussed it with @nikic in another review but I should have made that clear here). As far as I can tell the GlobalVariable cast is necessary to get at the DataLayout and to compute the offset below. (Or is there some other way to get at it?)

4287

The change prevents treating past-the-end accesses to char arrays the same was as those to empty strings, such as in strlen("123" + 4). This is exercised by str-int-3.ll that I added in D125114 based on my understanding of the convention that library calls that provably result in an out-of-bounds access are best left for sanitizers to report. (I think an argument can be made that folding such calls to zero is safer than counting on sanitizers, so I don't mind removing the check and adjusting the test if it's decided that's preferable.)

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4196

If you really want to avoid the DataLayout argument, you can do something like dyn_cast<GlobalVariable>(getUnderlyingObject(V)), take the DataLayout from there, and then use that to feed the stripAndAccumulateConstantOffsets() call.

Otherwise this is just shifting the problem to a GEP + bitcast + GEP sequence. (And it's worth noting that with opaque pointers the casts being skipped here don't exist anyway.)

[efriedma]

llvm/lib/Analysis/ValueTracking.cpp

4287

If we want getConstantStringInfo(TrimAtNul=true) to always fail if it doesn't trim a nul, we could do that, but only failing when we don't trim a null and Slice.Array is null doesn't really make sense to me.

[msebor]

• Have getConstantStringInfo fail for empty array slices when TrimAtNul is set.
• Have GetStringLengthH fail for empty array slices.
• Gracefully handle empty array slices in memchr and memrchr folders.
• Add tests.

llvm/lib/Analysis/ValueTracking.cpp

4196

Thanks for the pointer to getUnderlyingObj. Unless there is a form of the function that also computes the aggregate GEP offset I don't think using it here would be appropriate since the rest of the function then has to (again) iterate over the same chain of casts and GEPs to compute the offset. (Would enhancing getUnderlyingObjto compute the offset be appropriate? FWIW, GCC has at least two utility functions that do both.)

I'm not opposed to adding the DataLayout argument (quite the contrary), but as I explained, I avoided it in this patch to keep it from growing too big. If making this small incremental improvement first is a problem I can instead start by submitting a change to add the new argument. Let me know your preference.

Opaque pointers obviously obviate the casts, so once typed pointers completely disappear the code can be simplified, The removal of the FisrstIdx test will still be necessary to handle these use cases either way but that can be done then. Would you prefer to defer this whole patch until then?

4287

I've made the change you suggest in the updated patch. It has a fairly pervasive impact on the couple of dozen or so clients of the function. There are no tests for this case so I've developed and added a subset of of them in the updated patch. It was a nontrivial effort whose goal is orthogonal to this enhancement and that I think would have been better handled separately and by someone who's less ambivalent about the benefits of doing this than me. (The test coverage would ideally be extended to all supported functions but I leave that for some other time.)

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4196

stripAndAccumulateConstantOffsets() is the function that computes aggregate GEP offsets. getUnderlyingObject() is just a suggestion on how you can fetch the DataLayout without passing an argument. Basically the start of this function (down to line 4222) would become something like this:

auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(V));
if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
  return false; // Not based on constant global.

const DataLayout &DL = GV->getParent()->getDataLayout();
APInt Offset(DL.getIndexTypeSizeInBits(V->getType()), 0);
if (GV != P->stripAndAccumulateConstantOffsets(DL, Offset, /*AllowNonInbounds*/ true))
  return false; // Could not determine offset from GV.

4287

Possibly I'm misreading @efriedma's comment, but I think the suggestion here was to just drop the change you originally did from the patch. This doesn't seem to have any direct relation to the bitcast stripping part.

(For what it's worth, I think I've come around on the sanitizer issue from "we should accommodate sanitizers if it doesn't cost any effort" to "we should ignore sanitizers completely and optimize as aggressively as possible", because these little checks are not a principled solution anyway, but they always cause a lot of discussion about whether some particular case should be special-cased or not.)

[msebor]

Changes in revision 3 of the patch

• return a conservative result from getConstantDataArrayInfo for past-the-end offsets,
• adds comments to getConstantStringInfo and GetStringLengthH explaining the decision to return a conservative result for out-of-bounds offsets,
• fold empty sequences in optimizeMemRChr and optimizeMemRhr,
• add new and adjust existing tests.

llvm/lib/Analysis/ValueTracking.cpp

4196

I'm pretty sure (I think) I understood what you meant. My point is that a call to getUnderlyingObject has a linear complexity in the number of GEPs/casts, and so would a fully general recursive call to getConstantDataArrayInfo. They both walk the IR to find the underlying declaration. Calling the former from the latter would make the latter do double the work, with quadratic complexity in the number of GEPs.

The complexity could be kept linear by

• adding a DataLayout argument to getConstantDataArrayInfo
• having getUnderlyingObject also accumulate the offset from each GEP it strips on the way to the declaration of the object (it too would need a DataLayout argument).

Both changes seem useful to me independently of each other (and as I mentioned, a precedent for the getUnderlyingObject change is GCC's get_ref_base_and_extent utility function, among others).

But until at least the first is done, this patch handles a single cast + GEP + cast chain in O(N). Alternatively, I can add the DataLayout argument to getConstantDataArrayInfo first, and handle in O(N) arbitrarily long chains of cast/GEP sequences.

Having said all that, I have a feeling we might be talking past each other and this will not be the end of it.

4287

Okay, given that, I'm comfortable removing both the check and the case str-int-3.ll test that otherwise fails.

I've also updated the new strcall-no-nul.ll test to reflect the current behavior on trunk, and in addition removed the other checks I added to verify the opposite strategy. (Either way, being more consistent about this than the initial patch leads to churn that's strictly outside the scope of this enhancement.)

As an aside it would be helpful to capture somewhere the decision to fold even in spite of the effect on sanitizers so that we can point to it when the question comes up again in the future.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4196

There shouldn't be any quadratic complexity -- when using getUnderlyingObject/stripAndAccumulateConstantOffsets there is no need for getConstantDataArrayInfo itself to be recursive, all the offsets are accumulated within a single call.

You are right that there is some redundant work going on in that getUnderlyingObject will first find the base object, and then stripAndAccumulateConstantOffsets will accumulate offsets down to it, but it's still a linear walk, repeated twice, so complexity is still O(n).

(If we want to really get down to it, doing two walks will actually be faster in practice, because getUnderlyingObject is significantly faster than stripAndAccumulateConstantOffsets, which means that we can quickly discard any cases that aren't based on a constant GV. This is just a side note, we generally wouldn't specifically optimize for that.)

[msebor]

Changes in revision 4 of the patch:

• use getUnderlyingObject and stripAndAccumulateConstantOffsets and avoid recursion in getConstantDataArrayInfo,
• add tests to exercise long chain of GEPs.

llvm/lib/Analysis/ValueTracking.cpp

4196

Aah, that was my misunderstanding, sorry. I assumed stripAndAccumulateConstantOffsets and accumulateConstantOffset both operated on just a single GEP except that the former also stripped casts. It looks like the former actually iterates over all the GEPs and accumulates the offsets from all of them. So yes, that does work linearly.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4194

You can move this out of the GEPOperator block and also drop the stripPointerCasts() above (and the repeated checks of GV below it). All cases can be treated uniformly.

4239

I wouldn't claim that folding these is really "safer", it's just a (UB-based) optimization.

[msebor]

Changes in revision 5 of the patch:

• Simplify getConstantDataArrayInfo some more.
• Update comment.

llvm/lib/Analysis/ValueTracking.cpp

4194

Because stripAndAccumulateConstantOffsets is a member of the Value class and not one of GEPOperator. Nice, thanks!

4239

Many users would find replacing an undefined library call with a well-defined expression safer than letting the call take place and crash their program for example. I certainly do, but I see little point in arguing about it here.

[nikic]

Implementation LG, some notes on the tests.

llvm/test/Transforms/InstCombine/memchr-10.ll

21 ↗

(On Diff #440696)

Incomplete check line?

llvm/test/Transforms/InstCombine/memchr-9.ll

318

These check lines aren't correct and are probably just getting ignored. You need to pass something like --check-prefixes=CHECK,BE and --check-prefixes=CHECK,LE and regenerate check lines.

llvm/test/Transforms/InstCombine/strcall-no-nul.ll

142 ↗

(On Diff #440696)

This check line doesn't make a lot of sense ... the syntax is incorrect (and the incorrect syntax is repeated in the cases below) and the ret wouldn't make sense here anyway (because strlen returns an integer not a pointer). The TODO also seems outdated, as this already folds to 0.

llvm/test/Transforms/InstCombine/strnlen-1.ll

166 ↗

(On Diff #440696)

This TODO is probably not relevant anymore given the updated patch?

[msebor]

Thanks for the careful review!

llvm/test/Transforms/InstCombine/memchr-10.ll

21 ↗

(On Diff #440696)

It's intentional and documented above: the return value doesn't matter (i.e., it's indeterminate here). I didn't want to encode an expectation one way or the other.

llvm/test/Transforms/InstCombine/memchr-9.ll

318

Right. You do have a good eye for detail!

llvm/test/Transforms/InstCombine/strcall-no-nul.ll

142 ↗

(On Diff #440696)

I've fixed the strlen typo.

I hand-wrote all these lines and I realize not all of them are entirely correct. My main goal was to more prominently mark up the expected failures, but I was also hoping that llvm-lit would pick them up somehow and indicate when there are expected failures in the test. I've removed the rest of the XFAIL- lines from the final commit but, for future reference, is there a way to do what I want? (I couldn't find an example in the test suite that I didn't add myself.)

[nikic]

llvm/test/Transforms/InstCombine/strcall-no-nul.ll

142 ↗

(On Diff #440696)

It's possible to mark the entire test as XFAIL using XFAIL: *, but I don't think XFAIL interacts with FileCheck in any way.

General convention is to check for current codegen and put a TODO/FIXME if it's currently incorrect/suboptimal.

[fhahn]

It looks like Transforms/InstCombine/str-int-3.ll is failing on Darwin systems. The Darwin bots are currently down unfortunately though (https://green.lab.llvm.org/green/)

[fhahn]

In D128364#3618130, @fhahn wrote:

It looks like Transforms/InstCombine/str-int-3.ll is failing on Darwin systems. The Darwin bots are currently down unfortunately though (https://green.lab.llvm.org/green/)

GreenDragon is back up, please see https://green.lab.llvm.org/green/job/clang-stage1-cmake-RA-incremental/29787/testReport/LLVM/Transforms_InstCombine/str_int_3_ll/ for more details about the failing test. Please revert the patch if the fix requires more time.

[msebor]

In D128364#3618948, @fhahn wrote:

GreenDragon is back up, please see https://green.lab.llvm.org/green/job/clang-stage1-cmake-RA-incremental/29787/testReport/LLVM/Transforms_InstCombine/str_int_3_ll/ for more details about the failing test. Please revert the patch if the fix requires more time.

Thanks for the heads up. I'm not having any luck reproducing the failure with a cross for either i386-apple-darwin or x86_64-apple-darwin. Can you please provide more detail? (The full test output and the target triple, or anything else that might help reproduce it on x86_64 Linux.)

[msebor]

I've managed to reproduce it by changing the test case. It seems as though the test input of

%pa_0_0_32 = getelementptr [2 x %struct.A], [2 x %struct.A]* @a, i64 0, i64 0, i32 0, i64 32
%ia_0_0_32 = call i32 @atoi(i8* %pa_0_0_32)

is on Darwin transformed into

%ia_0_0_32 = call i32 @atoi(i8* getelementptr inbounds ([2 x %struct.A], [2 x %struct.A]* @a, i64 1, i64 0, i32 0, i64 0))

which the folder doesn't handle.

[msebor]

In D128364#3619404, @msebor wrote:

I've managed to reproduce it by changing the test case...

Sorry, I was too hasty, that works as expected. I still have not been able to reproduce it.

[msebor]

I suspect the Darwin strtol behaves differently than on Linux for en empty subject sequence (ie., for ""). On Linux strtol succeeds and returns zero without changing errno. On Darwin it sets errno, which then causes the convertStrToNumber utility function to fail. This is permitted by POSIX but the test assumes the Linux behavior.

This also seems be supported by the Apple open source implementation of the function in strtol.c.

[msebor]

I've relaxed the test in rGd515211a0ce1 to avoid exercising the target-dependent behavior. Please let me know if you see any other issues.

[spatel]

In D128364#3619587, @msebor wrote:

I've relaxed the test in rGd515211a0ce1 to avoid exercising the target-dependent behavior. Please let me know if you see any other issues.

That avoids the test failure, but we still have a host-platform difference that seems unnecessary.

IIUC, the problem is here:
https://github.com/llvm/llvm-project/blob/649439e7aeeb3b30f54297b3c6f7d6549fb2f85a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp#L87

On Linux, errno isn't set for an empty string:
https://godbolt.org/z/Tn5j1o4s6

But on a Mac (I tested locally - not sure if it's possible to do that on godbolt), I get this output:

Value of errno: 22
res = 0

Instead of return nullptr on errno, just remove that check? Or return a null constant since anything goes at that point?

[msebor]

I agree there is a detectable difference when folding either undefined calls to atoi (or strtol) either with past the end pointers, or even with the empty string. The former calls are undefined so the difference shouldn't matter, but the latter is well-defined. In the latter case the difference predates the patch which is why I just "papered" over it by disabling the test, but I agree it should be avoided in the well-defined case. I've raised PR 56293 to keep track of it and will look into removing it.

[xbolva00]

Maybe reland with better patch title as this patch affects more libcalls than just two ones?

llvm/lib/Analysis/ValueTracking.cpp

 bool llvm::getConstantDataArrayInfo(const Value *V,
                                     ConstantDataArraySlice &Slice,
                                     unsigned ElementSize, uint64_t Offset) {
   assert(V);
 
   // Look through bitcast instructions and geps.
   V = V->stripPointerCasts();
 
-  // If the value is a GEP instruction or constant expression, treat it as an
-  // offset.
   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
-    // Fail if the first GEP operand is not a constant zero and we're
-    // not indexing into the initializer.
-    const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1));
-    if (!FirstIdx || !FirstIdx->isZero())
-      return false;
-
+    // Drill down into the first operand, ignoring any intervening casts,
+    // and determine the identity of the referenced object along with
+    // the byte offset into it.
     Value *Op0 = GEP->getOperand(0);
+    Op0 = Op0->stripPointerCasts();
     const GlobalVariable *GV = dyn_cast<GlobalVariable>(Op0);
     if (!GV)
       return false;
 
     // Fail if the offset into the initializer is not constant.
     const DataLayout &DL = GV->getParent()->getDataLayout();
     APInt Off(DL.getIndexSizeInBits(GEP->getPointerAddressSpace()), 0);
     if (!GEP->accumulateConstantOffset(DL, Off))
       return false;

       // calls with them as arguments.
       return false;
 
     Slice.Array = nullptr;
     Slice.Offset = 0;
     Slice.Length = Length - Offset;
     return true;
   }
 
   auto *Init = const_cast<Constant *>(GV->getInitializer());
   if (auto *ArrayInit = dyn_cast<ConstantDataArray>(Init)) {
     Type *InitElTy = ArrayInit->getElementType();
     if (InitElTy->isIntegerTy(ElementSize)) {
       // If Init is an initializer for an array of the expected type
       // and size, use it as is.
       Array = ArrayInit;
       ArrayTy = ArrayInit->getType();

 /// If unsuccessful, it returns false.
 bool llvm::getConstantStringInfo(const Value *V, StringRef &Str,
                                  uint64_t Offset, bool TrimAtNul) {
   ConstantDataArraySlice Slice;
   if (!getConstantDataArrayInfo(V, Slice, 8, Offset))
     return false;
 
   if (Slice.Array == nullptr) {
-    if (TrimAtNul) {
+    if (Slice.Length && TrimAtNul) {
       Str = StringRef();
       return true;
     }
     if (Slice.Length == 1) {
       Str = StringRef("", 1);
       return true;
     }
     // We cannot instantiate a StringRef as we do not have an appropriate string

llvm/test/Transforms/InstCombine/memchr-9.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Verify that calls to memchr with arrays of elements larger than char
+; are folded correctly.
+; RUN: opt < %s -passes=instcombine -S -data-layout="E" | FileCheck %s
+; RUN: opt < %s -passes=instcombine -S -data-layout="e" | FileCheck %s
+;
+; Exercise folding of memchr calls with addition expressions involving
+; pointers into constant arrays of types larger than char and fractional
+; offsets.
+
+declare i8* @memchr(i8*, i32, i64)
+
+%struct.A = type { [2 x i16], [2 x i16] }
+
+; Hex byte representation: 00 00  01 01  02 02  03 03
+@a = constant [1 x %struct.A] [%struct.A { [2 x i16] [i16 0, i16 257], [2 x i16] [i16 514, i16 771] }]
+
+
+define void @fold_memchr_A_pIb_cst_cst(i8** %pchr) {
+; CHECK-LABEL: @fold_memchr_A_pIb_cst_cst(
+; CHECK-NEXT:    store i8* bitcast ([1 x %struct.A]* @a to i8*), i8** [[PCHR:%.*]], align 8
+; CHECK-NEXT:    [[PST_0_1_1:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 1
+; CHECK-NEXT:    store i8* null, i8** [[PST_0_1_1]], align 8
+; CHECK-NEXT:    [[PST_0_4_4:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 2
+; CHECK-NEXT:    store i8* null, i8** [[PST_0_4_4]], align 8
+; CHECK-NEXT:    [[PST_1_0_1:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 3
+; CHECK-NEXT:    store i8* getelementptr (i8, i8* bitcast ([1 x %struct.A]* @a to i8*), i64 1), i8** [[PST_1_0_1]], align 8
+; CHECK-NEXT:    [[PST_1_0_3:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 4
+; CHECK-NEXT:    store i8* getelementptr (i8, i8* bitcast ([1 x %struct.A]* @a to i8*), i64 1), i8** [[PST_1_0_3]], align 8
+; CHECK-NEXT:    [[PST_1_1_1:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 5
+; CHECK-NEXT:    store i8* null, i8** [[PST_1_1_1]], align 8
+; CHECK-NEXT:    [[PST_1_1_2:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 6
+; CHECK-NEXT:    store i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 0, i64 1) to i8*), i8** [[PST_1_1_2]], align 8
+; CHECK-NEXT:    [[PST_1_3_3:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 7
+; CHECK-NEXT:    store i8* null, i8** [[PST_1_3_3]], align 8
+; CHECK-NEXT:    [[PST_1_3_4:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 8
+; CHECK-NEXT:    store i8* null, i8** [[PST_1_3_4]], align 8
+; CHECK-NEXT:    [[PST_1_3_6:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 10
+; CHECK-NEXT:    store i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 1, i64 1) to i8*), i8** [[PST_1_3_6]], align 8
+; CHECK-NEXT:    ret void
+;
+  %pa = getelementptr [1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0
+  %pi8a = bitcast %struct.A* %pa to i8*
+
+  %pi8ap0 = getelementptr i8, i8* %pi8a, i32 0
+
+  ; Fold memchr((char*)a + 0, '\0', 1) to a.
+  %pst_0_0_1 = getelementptr i8*, i8** %pchr, i32 0
+  %chr_0_0_1 = call i8* @memchr(i8* %pi8ap0, i32 0, i64 1)
+  store i8* %chr_0_0_1, i8** %pst_0_0_1
+
+  ; Fold memchr((char*)a + 0, '\01', 1) to null.
+  %pst_0_1_1 = getelementptr i8*, i8** %pchr, i32 1
+  %chr_0_1_1 = call i8* @memchr(i8* %pi8ap0, i32 1, i64 1)
+  store i8* %chr_0_1_1, i8** %pst_0_1_1
+
+  ; Fold memchr((char*)a + 0, '\04', 4) to null.
+  %pst_0_4_4 = getelementptr i8*, i8** %pchr, i32 2
+  %chr_0_4_4 = call i8* @memchr(i8* %pi8ap0, i32 4, i64 4)
+  store i8* %chr_0_4_4, i8** %pst_0_4_4
+
+
+  %pi8ap1 = getelementptr i8, i8* %pi8a, i32 1
+
+  ; Fold memchr((char*)a + 1, '\0', 1) to (char*)a + 1.
+  %pst_1_0_1 = getelementptr i8*, i8** %pchr, i32 3
+  %chr_1_0_1 = call i8* @memchr(i8* %pi8ap1, i32 0, i64 1)
+  store i8* %chr_1_0_1, i8** %pst_1_0_1
+
+  ; Fold memchr((char*)a + 1, '\0', 3) to (char*)a + 1.
+  %pst_1_0_3 = getelementptr i8*, i8** %pchr, i32 4
+  %chr_1_0_3 = call i8* @memchr(i8* %pi8ap1, i32 0, i64 3)
+  store i8* %chr_1_0_3, i8** %pst_1_0_3
+
+  ; Fold memchr((char*)a + 1, '\01', 1) to null.
+  %pst_1_1_1 = getelementptr i8*, i8** %pchr, i32 5
+  %chr_1_1_1 = call i8* @memchr(i8* %pi8ap1, i32 1, i64 1)
+  store i8* %chr_1_1_1, i8** %pst_1_1_1
+
+  ; Fold memchr((char*)a + 1, '\01', 2) to (char*)a + 2.
+  %pst_1_1_2 = getelementptr i8*, i8** %pchr, i32 6
+  %chr_1_1_2 = call i8* @memchr(i8* %pi8ap1, i32 1, i64 2)
+  store i8* %chr_1_1_2, i8** %pst_1_1_2
+
+  ; Fold memchr((char*)a + 1, '\03', 3) to null.
+  %pst_1_3_3 = getelementptr i8*, i8** %pchr, i32 7
+  %chr_1_3_3 = call i8* @memchr(i8* %pi8ap1, i32 3, i64 3)
+  store i8* %chr_1_3_3, i8** %pst_1_3_3
+
+  ; Fold memchr((char*)a + 1, '\03', 4) to null.
+  %pst_1_3_4 = getelementptr i8*, i8** %pchr, i32 8
+  %chr_1_3_4 = call i8* @memchr(i8* %pi8ap1, i32 3, i64 4)
+  store i8* %chr_1_3_4, i8** %pst_1_3_4
+
+  ; Fold memchr((char*)a + 1, '\03', 5) to null.
+  %pst_1_3_5 = getelementptr i8*, i8** %pchr, i32 9
+  %chr_1_3_5 = call i8* @memchr(i8* %pi8ap1, i32 3, i64 5)
+  store i8* %chr_1_3_4, i8** %pst_1_3_4
+
+  ; Fold memchr((char*)a + 1, '\03', 6) to (char*)a + 5.
+  %pst_1_3_6 = getelementptr i8*, i8** %pchr, i32 10
+  %chr_1_3_6 = call i8* @memchr(i8* %pi8ap1, i32 3, i64 6)
+  store i8* %chr_1_3_6, i8** %pst_1_3_6
+
+
+  ret void
+}
+
+
+define void @fold_memchr_A_pIb_cst_N(i64 %N, i8** %pchr) {
+; CHECK-LABEL: @fold_memchr_A_pIb_cst_N(
+; CHECK-NEXT:    [[MEMCHR_CMP:%.*]] = icmp eq i64 [[N:%.*]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[MEMCHR_CMP]], i8* null, i8* bitcast ([1 x %struct.A]* @a to i8*)
+; CHECK-NEXT:    store i8* [[TMP1]], i8** [[PCHR:%.*]], align 8
+; CHECK-NEXT:    [[PST_0_1_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 1
+; CHECK-NEXT:    [[MEMCHR_CMP1:%.*]] = icmp ult i64 [[N]], 3
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[MEMCHR_CMP1]], i8* null, i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 0, i64 1) to i8*)
+; CHECK-NEXT:    store i8* [[TMP2]], i8** [[PST_0_1_N]], align 8
+; CHECK-NEXT:    [[PST_0_4_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 2
+; CHECK-NEXT:    store i8* null, i8** [[PST_0_4_N]], align 8
+; CHECK-NEXT:    [[PST_1_0_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 3
+; CHECK-NEXT:    [[MEMCHR_CMP2:%.*]] = icmp eq i64 [[N]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[MEMCHR_CMP2]], i8* null, i8* getelementptr (i8, i8* bitcast ([1 x %struct.A]* @a to i8*), i64 1)
+; CHECK-NEXT:    store i8* [[TMP3]], i8** [[PST_1_0_N]], align 8
+; CHECK-NEXT:    [[PST_1_1_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 4
+; CHECK-NEXT:    [[MEMCHR_CMP3:%.*]] = icmp ult i64 [[N]], 2
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[MEMCHR_CMP3]], i8* null, i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 0, i64 1) to i8*)
+; CHECK-NEXT:    store i8* [[TMP4]], i8** [[PST_1_1_N]], align 8
+; CHECK-NEXT:    [[PST_1_2_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 5
+; CHECK-NEXT:    [[MEMCHR_CMP4:%.*]] = icmp ult i64 [[N]], 4
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[MEMCHR_CMP4]], i8* null, i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 1, i64 0) to i8*)
+; CHECK-NEXT:    store i8* [[TMP5]], i8** [[PST_1_2_N]], align 8
+; CHECK-NEXT:    [[PST_1_3_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 6
+; CHECK-NEXT:    [[MEMCHR_CMP5:%.*]] = icmp ult i64 [[N]], 6
+; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[MEMCHR_CMP5]], i8* null, i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 1, i64 1) to i8*)
+; CHECK-NEXT:    store i8* [[TMP6]], i8** [[PST_1_3_N]], align 8
+; CHECK-NEXT:    [[PST_1_4_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 7
+; CHECK-NEXT:    store i8* null, i8** [[PST_1_4_N]], align 8
+; CHECK-NEXT:    [[PST_2_0_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 8
+; CHECK-NEXT:    store i8* null, i8** [[PST_2_0_N]], align 8
+; CHECK-NEXT:    [[PST_2_1_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 9
+; CHECK-NEXT:    [[MEMCHR_CMP6:%.*]] = icmp eq i64 [[N]], 0
+; CHECK-NEXT:    [[TMP7:%.*]] = select i1 [[MEMCHR_CMP6]], i8* null, i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 0, i64 1) to i8*)
+; CHECK-NEXT:    store i8* [[TMP7]], i8** [[PST_2_1_N]], align 8
+; CHECK-NEXT:    [[PST_2_2_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 10
+; CHECK-NEXT:    [[MEMCHR_CMP7:%.*]] = icmp ult i64 [[N]], 3
+; CHECK-NEXT:    [[TMP8:%.*]] = select i1 [[MEMCHR_CMP7]], i8* null, i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 1, i64 0) to i8*)
+; CHECK-NEXT:    store i8* [[TMP8]], i8** [[PST_2_2_N]], align 8
+; CHECK-NEXT:    [[PST_2_3_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 11
+; CHECK-NEXT:    [[MEMCHR_CMP8:%.*]] = icmp ult i64 [[N]], 5
+; CHECK-NEXT:    [[TMP9:%.*]] = select i1 [[MEMCHR_CMP8]], i8* null, i8* bitcast (i16* getelementptr inbounds ([1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0, i32 1, i64 1) to i8*)
+; CHECK-NEXT:    store i8* [[TMP9]], i8** [[PST_2_3_N]], align 8
+; CHECK-NEXT:    [[PST_2_4_N:%.*]] = getelementptr i8*, i8** [[PCHR]], i64 12
+; CHECK-NEXT:    store i8* null, i8** [[PST_2_4_N]], align 8
+; CHECK-NEXT:    ret void
+;
+  %pa = getelementptr [1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0
+  %pi8a = bitcast %struct.A* %pa to i8*
+
+  %pi8ap0 = getelementptr i8, i8* %pi8a, i32 0
+
+  ; Fold memchr((char*)a + 0, '\0', N) to N ? a : null.
+  %pst_0_0_n = getelementptr i8*, i8** %pchr, i32 0
+  %chr_0_0_n = call i8* @memchr(i8* %pi8ap0, i32 0, i64 %N)
+  store i8* %chr_0_0_n, i8** %pst_0_0_n
+
+  ; Fold memchr((char*)a + 0, '\01', N) to N < 2 ? null : a.
+  %pst_0_1_n = getelementptr i8*, i8** %pchr, i32 1
+  %chr_0_1_n = call i8* @memchr(i8* %pi8ap0, i32 1, i64 %N)
+  store i8* %chr_0_1_n, i8** %pst_0_1_n
+
+  ; Fold memchr((char*)a + 0, '\04', N) to null.
+  %pst_0_4_n = getelementptr i8*, i8** %pchr, i32 2
+  %chr_0_4_n = call i8* @memchr(i8* %pi8ap0, i32 4, i64 %N)
+  store i8* %chr_0_4_n, i8** %pst_0_4_n
+
+
+  %pi8ap1 = getelementptr i8, i8* %pi8a, i32 1
+
+  ; Fold memchr((char*)a + 1, '\0', N) to null.
+  %pst_1_0_n = getelementptr i8*, i8** %pchr, i32 3
+  %chr_1_0_n = call i8* @memchr(i8* %pi8ap1, i32 0, i64 %N)
+  store i8* %chr_1_0_n, i8** %pst_1_0_n
+
+  ; Fold memchr((char*)a + 1, '\01', N) N ? (char*)a + 1 : null.
+  %pst_1_1_n = getelementptr i8*, i8** %pchr, i32 4
+  %chr_1_1_n = call i8* @memchr(i8* %pi8ap1, i32 1, i64 %N)
+  store i8* %chr_1_1_n, i8** %pst_1_1_n
+
+  ; Fold memchr((char*)a + 1, '\02', N) to N < 2 ? null : (char*)a + 4.
+  %pst_1_2_n = getelementptr i8*, i8** %pchr, i32 5
+  %chr_1_2_n = call i8* @memchr(i8* %pi8ap1, i32 2, i64 %N)
+  store i8* %chr_1_2_n, i8** %pst_1_2_n
+
+  ; Fold memchr((char*)a + 1, '\03', N) to N < 6 ? null : (char*)a + 6.
+  %pst_1_3_n = getelementptr i8*, i8** %pchr, i32 6
+  %chr_1_3_n = call i8* @memchr(i8* %pi8ap1, i32 3, i64 %N)
+  store i8* %chr_1_3_n, i8** %pst_1_3_n
+
+  ; Fold memchr((char*)a + 1, '\04', N) to null.
+  %pst_1_4_n = getelementptr i8*, i8** %pchr, i32 7
+  %chr_1_4_n = call i8* @memchr(i8* %pi8ap1, i32 4, i64 %N)
+  store i8* %chr_1_4_n, i8** %pst_1_4_n
+
+
+  %pi8ap2 = getelementptr i8, i8* %pi8a, i32 2
+
+  ; Fold memchr((char*)a + 2, '\0', N) to null.
+  %pst_2_0_n = getelementptr i8*, i8** %pchr, i32 8
+  %chr_2_0_n = call i8* @memchr(i8* %pi8ap2, i32 0, i64 %N)
+  store i8* %chr_2_0_n, i8** %pst_2_0_n
+
+  ; Fold memchr((char*)a + 2, '\01', N) N ? (char*)a + 2 : null.
+  %pst_2_1_n = getelementptr i8*, i8** %pchr, i32 9
+  %chr_2_1_n = call i8* @memchr(i8* %pi8ap2, i32 1, i64 %N)
+  store i8* %chr_2_1_n, i8** %pst_2_1_n
+
+  ; Fold memchr((char*)a + 2, '\02', N) to N < 3 ? null : (char*)a + 2.
+  %pst_2_2_n = getelementptr i8*, i8** %pchr, i32 10
+  %chr_2_2_n = call i8* @memchr(i8* %pi8ap2, i32 2, i64 %N)
+  store i8* %chr_2_2_n, i8** %pst_2_2_n
+
+  ; Fold memchr((char*)a + 2, '\03', N) to N < 5 ? null : (char*)a + 4.
+  %pst_2_3_n = getelementptr i8*, i8** %pchr, i32 11
+  %chr_2_3_n = call i8* @memchr(i8* %pi8ap2, i32 3, i64 %N)
+  store i8* %chr_2_3_n, i8** %pst_2_3_n
+
+  ; Fold memchr((char*)a + 2, '\04', N) to null.
+  %pst_2_4_n = getelementptr i8*, i8** %pchr, i32 12
+  %chr_2_4_n = call i8* @memchr(i8* %pi8ap2, i32 4, i64 %N)
+  store i8* %chr_2_4_n, i8** %pst_2_4_n
+
+  ret void
+}
+
+
+; Verify that calls with out of bounds offsets are not folded.
+
+define void @call_memchr_A_pIb_xs_cst(i8** %pchr) {
+; CHECK-LABEL: @call_memchr_A_pIb_xs_cst(
+;
+; Verify that the call isn't folded when the first GEP index is excessive.
+  %pa1 = getelementptr [1 x %struct.A], [1 x %struct.A]* @a, i64 1, i64 0
+  %pi8a1 = bitcast %struct.A* %pa1 to i8*
+
+  %pi8a1p0 = getelementptr i8, i8* %pi8a1, i32 0
+
+  ; Don't fold memchr((char*)&a[1] + 0, '\0', 2).
+  %pst_1_0_0_2 = getelementptr i8*, i8** %pchr, i32 0
+  %chr_1_0_0_2 = call i8* @memchr(i8* %pi8a1p0, i32 0, i64 2)
+  store i8* %chr_1_0_0_2, i8** %pst_1_0_0_2
+
+  %pi8a1p1 = getelementptr i8, i8* %pi8a1, i32 1
+
+  ; Likewise, don't fold memchr((char*)&a[1] + 1, '\0', 2).
+  %pst_1_0_1_2 = getelementptr i8*, i8** %pchr, i32 1
+  %chr_1_0_1_2 = call i8* @memchr(i8* %pi8a1p0, i32 0, i64 2)
+  store i8* %chr_1_0_1_2, i8** %pst_1_0_1_2
+
+; Verify that the call isn't folded when the first GEP index is in bounds
+; but the byte offset is excessive.
+  %pa0 = getelementptr [1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0
+  %pi8a0 = bitcast %struct.A* %pa0 to i8*
+
+  %pi8a0p8 = getelementptr i8, i8* %pi8a0, i32 8
+
+  ; Don't fold memchr((char*)&a[0] + 8, '\0', 2).
+  %pst_0_0_8_2 = getelementptr i8*, i8** %pchr, i32 2
+  %chr_0_0_8_2 = call i8* @memchr(i8* %pi8a0p8, i32 0, i64 2)
+  store i8* %chr_0_0_8_2, i8** %pst_0_0_8_2
+
+  ret void
+}

llvm/test/Transforms/InstCombine/memcmp-7.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+;
+; Exercise folding of memcmp calls with addition expressions involving
+; pointers into constant arrays of types larger than char and fractional
+; offsets.
+
+declare i32 @memcmp(i8*, i8*, i64)
+
+@i32a = constant [2 x i16] [i16 4386, i16 13124]
+@i32b = constant [2 x i16] [i16 4386, i16 13124]
+
+
+define void @fold_memcmp_i32a_i32b_pIb(i32 %I, i32* %pcmp)
+; CHECK-LABEL: @fold_memcmp_i32a_i32b_pIb(
+; CHECK-NEXT:    store i32 0, i32* [[PCMP:%.*]], align 4
+; CHECK-NEXT:    [[PST_1_1_2:%.*]] = getelementptr i32, i32* [[PCMP]], i64 1
+; CHECK-NEXT:    store i32 0, i32* [[PST_1_1_2]], align 4
+; CHECK-NEXT:    [[PST_1_1_3:%.*]] = getelementptr i32, i32* [[PCMP]], i64 2
+; CHECK-NEXT:    store i32 0, i32* [[PST_1_1_3]], align 4
+; CHECK-NEXT:    ret void
+;
+{
+  %pi32a = getelementptr [2 x i16], [2 x i16]* @i32a, i32 0, i32 0
+  %pi32b = getelementptr [2 x i16], [2 x i16]* @i32b, i32 0, i32 0
+
+  %pi8a = bitcast i16* %pi32a to i8*
+  %pi8b = bitcast i16* %pi32b to i8*
+
+  %pi8ap1 = getelementptr i8, i8* %pi8a, i32 1
+  %pi8bp1 = getelementptr i8, i8* %pi8b, i32 1
+
+  %pst_1_1_1 = getelementptr i32, i32* %pcmp, i32 0
+  %cmp_1_1_1 = call i32 @memcmp(i8* %pi8ap1, i8* %pi8ap1, i64 1)
+  store i32 %cmp_1_1_1, i32* %pst_1_1_1
+
+  %pst_1_1_2 = getelementptr i32, i32* %pcmp, i32 1
+  %cmp_1_1_2 = call i32 @memcmp(i8* %pi8ap1, i8* %pi8ap1, i64 2)
+  store i32 %cmp_1_1_2, i32* %pst_1_1_2
+
+  %pst_1_1_3 = getelementptr i32, i32* %pcmp, i32 2
+  %cmp_1_1_3 = call i32 @memcmp(i8* %pi8ap1, i8* %pi8ap1, i64 3)
+  store i32 %cmp_1_1_3, i32* %pst_1_1_3
+
+  ret void
+}
+
+
+%struct.A = type { [4 x i8] }
+%struct.B = type { [2 x i8], [2 x i8] }
+
+@a = constant [1 x %struct.A] [%struct.A { [4 x i8] [i8 1, i8 2, i8 3, i8 4] }]
+@b = constant [1 x %struct.B] [%struct.B { [2 x i8] [i8 1, i8 2], [2 x i8] [i8 3, i8 4]}]
+
+define void @fold_memcmp_A_B_pIb(i32 %I, i32* %pcmp) {
+; CHECK-LABEL: @fold_memcmp_A_B_pIb(
+; CHECK-NEXT:    store i32 0, i32* [[PCMP:%.*]], align 4
+; CHECK-NEXT:    [[PST_0_0_2:%.*]] = getelementptr i32, i32* [[PCMP]], i64 1
+; CHECK-NEXT:    store i32 0, i32* [[PST_0_0_2]], align 4
+; CHECK-NEXT:    [[PST_0_0_3:%.*]] = getelementptr i32, i32* [[PCMP]], i64 2
+; CHECK-NEXT:    store i32 0, i32* [[PST_0_0_3]], align 4
+; CHECK-NEXT:    [[PST_0_0_4:%.*]] = getelementptr i32, i32* [[PCMP]], i64 3
+; CHECK-NEXT:    store i32 0, i32* [[PST_0_0_4]], align 4
+; CHECK-NEXT:    [[PST_0_1_1:%.*]] = getelementptr i32, i32* [[PCMP]], i64 4
+; CHECK-NEXT:    store i32 -1, i32* [[PST_0_1_1]], align 4
+; CHECK-NEXT:    [[PST_0_1_2:%.*]] = getelementptr i32, i32* [[PCMP]], i64 5
+; CHECK-NEXT:    store i32 -1, i32* [[PST_0_1_2]], align 4
+; CHECK-NEXT:    [[PST_0_1_3:%.*]] = getelementptr i32, i32* [[PCMP]], i64 6
+; CHECK-NEXT:    store i32 -1, i32* [[PST_0_1_3]], align 4
+; CHECK-NEXT:    [[PST_1_0_1:%.*]] = getelementptr i32, i32* [[PCMP]], i64 4
+; CHECK-NEXT:    store i32 1, i32* [[PST_1_0_1]], align 4
+; CHECK-NEXT:    [[PST_1_0_2:%.*]] = getelementptr i32, i32* [[PCMP]], i64 5
+; CHECK-NEXT:    store i32 1, i32* [[PST_1_0_2]], align 4
+; CHECK-NEXT:    [[PST_1_0_3:%.*]] = getelementptr i32, i32* [[PCMP]], i64 6
+; CHECK-NEXT:    store i32 1, i32* [[PST_1_0_3]], align 4
+; CHECK-NEXT:    ret void
+;
+  %pa = getelementptr [1 x %struct.A], [1 x %struct.A]* @a, i64 0, i64 0
+  %pb = getelementptr [1 x %struct.B], [1 x %struct.B]* @b, i64 0, i64 0
+
+  %pi8a = bitcast %struct.A* %pa to i8*
+  %pi8b = bitcast %struct.B* %pb to i8*
+
+  %pi8ap0 = getelementptr i8, i8* %pi8a, i32 0
+  %pi8bp0 = getelementptr i8, i8* %pi8b, i32 0
+
+  ; Fold memcmp(&a, &b, 1) to 0;
+  %pst_0_0_1 = getelementptr i32, i32* %pcmp, i32 0
+  %cmp_0_0_1 = call i32 @memcmp(i8* %pi8ap0, i8* %pi8bp0, i64 1)
+  store i32 %cmp_0_0_1, i32* %pst_0_0_1
+
+  ; Fold memcmp(&a, &b, 2) to 0;
+  %pst_0_0_2 = getelementptr i32, i32* %pcmp, i32 1
+  %cmp_0_0_2 = call i32 @memcmp(i8* %pi8ap0, i8* %pi8bp0, i64 2)
+  store i32 %cmp_0_0_2, i32* %pst_0_0_2
+
+  ; Fold memcmp(&a, &b, 3) to 0;
+  %pst_0_0_3 = getelementptr i32, i32* %pcmp, i32 2
+  %cmp_0_0_3 = call i32 @memcmp(i8* %pi8ap0, i8* %pi8bp0, i64 3)
+  store i32 %cmp_0_0_3, i32* %pst_0_0_3
+
+  ; Fold memcmp(&a, &b, 4) to 0;
+  %pst_0_0_4 = getelementptr i32, i32* %pcmp, i32 3
+  %cmp_0_0_4 = call i32 @memcmp(i8* %pi8ap0, i8* %pi8bp0, i64 4)
+  store i32 %cmp_0_0_4, i32* %pst_0_0_4
+
+
+  %pi8bp1 = getelementptr i8, i8* %pi8b, i32 1
+
+  ; Fold memcmp(&a, (char*)&b + 1, 1) to -1;
+  %pst_0_1_1 = getelementptr i32, i32* %pcmp, i32 4
+  %cmp_0_1_1 = call i32 @memcmp(i8* %pi8ap0, i8* %pi8bp1, i64 1)
+  store i32 %cmp_0_1_1, i32* %pst_0_1_1
+
+  ; Fold memcmp(&a, (char*)&b + 1, 2) to -1;
+  %pst_0_1_2 = getelementptr i32, i32* %pcmp, i32 5
+  %cmp_0_1_2 = call i32 @memcmp(i8* %pi8ap0, i8* %pi8bp1, i64 2)
+  store i32 %cmp_0_1_2, i32* %pst_0_1_2
+
+  ; Fold memcmp(&a, (char*)&b + 1, 3) to -1;
+  %pst_0_1_3 = getelementptr i32, i32* %pcmp, i32 6
+  %cmp_0_1_3 = call i32 @memcmp(i8* %pi8ap0, i8* %pi8bp1, i64 3)
+  store i32 %cmp_0_1_3, i32* %pst_0_1_3
+
+
+  %pi8ap1 = getelementptr i8, i8* %pi8a, i32 1
+
+  ; Fold memcmp((char*)&a + 1, &b, 1) to +1;
+  %pst_1_0_1 = getelementptr i32, i32* %pcmp, i32 4
+  %cmp_1_0_1 = call i32 @memcmp(i8* %pi8ap1, i8* %pi8bp0, i64 1)
+  store i32 %cmp_1_0_1, i32* %pst_1_0_1
+
+  ; Fold memcmp((char*)&a + 1, &b, 2) to +1;
+  %pst_1_0_2 = getelementptr i32, i32* %pcmp, i32 5
+  %cmp_1_0_2 = call i32 @memcmp(i8* %pi8ap1, i8* %pi8bp0, i64 2)
+  store i32 %cmp_1_0_2, i32* %pst_1_0_2
+
+  ; Fold memcmp((char*)&a + 1, &b, 3) to +1;
+  %pst_1_0_3 = getelementptr i32, i32* %pcmp, i32 6
+  %cmp_1_0_3 = call i32 @memcmp(i8* %pi8ap1, i8* %pi8bp0, i64 3)
+  store i32 %cmp_1_0_3, i32* %pst_1_0_3
+
+  ret void
+}