[AggressiveInstCombine] folding load for constant global patterened arrays and structs by alignment

[khei4]

Summary

Fold loadInst for constant aggregate types, those load results are equivalent for the given alignments.

This revision will be part 1 of the following stages.

1. alignment-based (This revision will be)
2. GEP-based https://reviews.llvm.org/D146622

• add ConstantFoldLoadFromPatternedAggregate method to AggressiveInstCombine

alive proofs: https://alive2.llvm.org/ce/z/qBGl72
Depends on: https://reviews.llvm.org/D145355
Fixes: https://github.com/rust-lang/rust/issues/107208.

[khei4]

update failed tests

[khei4]

add inline comments for check and review.

llvm/lib/Analysis/ConstantFolding.cpp

778 ↗

(On Diff #500393)

although I'm not sure it's possible to fold pointer structs and arrays, note here.

813 ↗

(On Diff #500393)

Conversion from bytes to the load type seems a bit ugly. Are there any better ways?

llvm/test/CodeGen/AMDGPU/lower-module-lds-via-hybrid.ll

22 ↗

(On Diff #500393)

update these tests llvm/test/CodeGen/AMDGPU/lower-module-lds-via-table.ll and llvm/test/CodeGen/AMDGPU/lower-module-lds-via-hybrid.ll by following commands

llvm/utils/update_test_checks.py --opt-binary ./build/bin/opt \
                                                                llvm/test/CodeGen/AMDGPU/lower-module-lds-via-table.ll
llvm/utils/update_llc_test_checks.py --llc-binary ./build/bin/llc \
                                                                llvm/test/CodeGen/AMDGPU/lower-module-lds-via-table.ll

and tweak head comments, as comments in these files say
Is this ok?

llvm/test/Transforms/InstSimplify/load-patterned-aggregates.ll

52

these tests are dupplicate to the following tests, sorry for the noises

[khei4]

@JonChesterfield Hi. Sorry for the sudden review requests. I modified the test files you recently modified. I don't know how to check diffs in this revision are correct or not.
Could you take a look at whether these changes are no problem? If you have any idea about these diffs please teach me, and I'll fix these diffs. :)

[khei4]

add pre-increment and overflow check

[khei4]

early return and format

[khei4]

@JonChesterfield @arsenm sorry for being noisy. I noticed my transformation was broken for ptrtoinst applied pointer arrays. I'll fix them.

[khei4]

see ReadDataFromGlobal return value.
now ready for review

[nikic]

llvm/lib/Analysis/ConstantFolding.cpp

781 ↗

(On Diff #500556)

This looks like a leftover from a previous implementation? I don't think your current one has any limitations regarding the type of the initializer.

786 ↗

(On Diff #500556)

If we have a 64K global and are reading 4 byte elements (i32) from it, then we need to check that 16k elements are the same. This is too expensive, as the compile-time regression shows.

We should limit this more aggressively to achieve reasonable compile-times, e.g. to 1K globals.

794 ↗

(On Diff #500556)

Rather than ReadDataFromGlobal(), we should use ConstantFoldLoadFromConst() here (or rather in the loop below). This has two advantages: It's going to handle all types (including pointer loads), and it allows an early bailout if not all elements are the same. Your current implementation will always read the entire global, even if it's clear after two elements that it's not uniform.

It will also take care of endianness itself.

798 ↗

(On Diff #500556)

If the load alignment is used, you also need to make sure that the global alignment is >= the load alignment. Otherwise it doesn't really tell you anything.

Though I'm not sure we really want to use alignment to determine access stride -- this is pretty unusual. Based this on the getelementptr stride would be more typical and handle cases that alignment can't (e.g. non-power-of-two stride).

llvm/lib/Analysis/InstructionSimplify.cpp

6640 ↗

(On Diff #500556)

hasUniqueInitializer() is only relevant if you want to modify an initializer, it should not be checked here.

6651 ↗

(On Diff #500556)

It might make sense to move this to the else of the below branch. If we know a constant offset, then we don't need to go through this code.

llvm/test/Transforms/InstSimplify/load-patterned-aggregates.ll

0

Rather than hardcoding the data layout, it's better to do something like this:

; RUN: opt < %s -passes=instsimplify -S -data-layout="e" | FileCheck %s --check-prefixes=CHECK,LE
; RUN: opt < %s -passes=instsimplify -S -data-layout="E" | FileCheck %s --check-prefixes=CHECK,BE

This will check both little and big endian.

[nikic]

it might be better to move this to aggressive inst-combine or refactor

Based on those numbers, it does seem pretty likely that we'll have to move this into AggressiveInstCombine. That would also give a bit more leeway wrt globals sizes. And I don't think it would really reduce optimization potential in any meaningful way -- this doesn't seem like the kind of fold that benefits from being run 20 times in the optimization pipeline.

[khei4]

Thank you for the review!

llvm/lib/Analysis/ConstantFolding.cpp

781 ↗

(On Diff #500556)

I might have cared padding bit, but it's no longer needed if I use ConstantFoldLoadFromConst

786 ↗

(On Diff #500556)

Sounds reasonable. I should have estimated it.

794 ↗

(On Diff #500556)

Rather than ReadDataFromGlobal(), we should use ConstantFoldLoadFromConst() here (or rather in the loop below). This has two advantages: It's going to handle all types (including pointer loads), and it allows an early bailout if not all elements are the same. Your current implementation will always read the entire global, even if it's clear after two elements that it's not uniform.
It will also take care of endianness itself.

Thank you! I couldn't notice that function. That sounds much more efficient than the current whole global variable reading.

798 ↗

(On Diff #500556)

If the load alignment is used, you also need to make sure that the global alignment is >= the load alignment. Otherwise it doesn't really tell you anything.

Right. I'll handle that case.

Based this on the getelementptr stride would be more typical and handle cases that alignment can't (e.g. non-power-of-two stride)

Ok, I am a little confused. Overall I thought I don't need to care about the case that alive decides any value could be returned. Although I didn't, undef value could be returned?

• if Global Variable's alignment > load's alignment, then whatever offsetted pointer is given to load, then any value could be returned.

https://alive2.llvm.org/ce/z/5_EDLB

• even if Global Variable's alignment <= load's alignment, the offset is not the multiple of load's alignment, then any value could be returned.

https://alive2.llvm.org/ce/z/Qnon4K

based on these assumptions, I used alignment to calculate possible valid accessible offsets. Are these assumptions and alive results correct?
I might have misunderstood or broadly interpret alive results.

But I'm feeling it's also good to compute stride from GEP and use a bigger one. A possible minimum stride can be gained by calculating the greatest common divisor of GEP-type sizes, so it's simpler than I expected.
(This might be out of scope, it might be better not to use GEP idx, I saw your proposal )

llvm/lib/Analysis/InstructionSimplify.cpp

6640 ↗

(On Diff #500556)

Yeah, you're also right here. I removed it. Thanks!

6651 ↗

(On Diff #500556)

Sounds reasonable. I'll fix.

llvm/test/Transforms/InstSimplify/load-patterned-aggregates.ll

0

Cool! Thanks!

[khei4]

Applied feedback

currently pushed and waiting to see the compile-time regressions expecting improvement ;)

https://llvm-compile-time-tracker.com/

[khei4]

leave some comments to consider.

llvm/lib/Analysis/ConstantFolding.cpp

773 ↗

(On Diff #501805)

Is it better to implement on GEPOperator?

798 ↗

(On Diff #500556)

Is the following case the example that only the seeing only GEP stride can't fold possible case?
https://alive2.llvm.org/ce/z/9cVcee

[khei4]

In D144445#4155524, @nikic wrote:

it might be better to move this to aggressive inst-combine or refactor

Based on those numbers, it does seem pretty likely that we'll have to move this into AggressiveInstCombine. That would also give a bit more leeway wrt globals sizes. And I don't think it would really reduce optimization potential in any meaningful way -- this doesn't seem like the kind of fold that benefits from being run 20 times in the optimization pipeline.

https://llvm-compile-time-tracker.com/compare.php?from=6f3baf43820680841b0daebdde2c78b43175444b&to=c08adfbed285199cd839da40419f918ac7a863b1&stat=instructions:u

@nikic
Thanks to your feedback, regression relaxed, but yet seems so much to stay here. I'll move this to AggressiveInstCombine.

[khei4]

move folding to AggressiveInstCombine

[khei4]

compile time regression for looking up to
64K objects: https://llvm-compile-time-tracker.com/compare.php?from=6f3baf43820680841b0daebdde2c78b43175444b&to=5024fc0c38730b0e58146a809b570d579d40fc0e&stat=instructions:u

1K objects: https://llvm-compile-time-tracker.com/compare.php?from=6f3baf43820680841b0daebdde2c78b43175444b&to=4a9358337b66c68e00462fac2c4902cb34398bd6&stat=instructions:u

other numbers (roughly) https://llvm-compile-time-tracker.com/?config=NewPM-O3&stat=instructions%3Au&remote=khei4

4K or 16K would be fine.

[khei4]

change the size bounds to 4K and add comments

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

904

according to this alive results https://alive2.llvm.org/ce/z/5_EDLB

when load alignment is bigger, seems to be fine to return poison value

if (GV->getAlign().valueOrOne().value() < LoadAlign) {
  I.replaceAllUsesWith(PoisonValue::get(LoadTy));
  return true;
}

but the following test failed. (on check-llvm only targeted for X86)
llvm/test/Transforms/PhaseOrdering/X86/nancvt.ll

is this alive result wrong?

[nikic]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

876

This isn't the right way to compute the GEP stride: GEP works on alloc sizes rather than store sizes, and can have multiple indices. You can use the collectOffset() methods to handle all the cases, and then GreatestCommonDivisor() to calculate the GCD.

894

This needs to bail out for volatile loads.

901

This is still checking for unique initializers -- should only check definitive initializer.

909

Even if we can't use the alignment, we can still use the GEP stride.

921

Can just omit the Offset argument here (it's zero by default).

929

Do we need the LoadSize adjustment here? Can we instead iterate to ByteOffset < GVSize?

The current LoadSize calculation is not right for pointers, but it seem like we can just drop it entirely.

933

It's okay to just use 64 as the APInt size in this context. You are currently using the size of the initializer, which will make for a *very* wide integer...

[khei4]

apply feedbacks.

[khei4]

update tests

[khei4]

Thank you for the review! I'm sorry about the messy changes!
also add ptr array and constant offsets tests. https://reviews.llvm.org/D145355

I'm now wondering to handle pointers. And mentioned behavior for cross-bounding load and bigger load variable alignment. I'll figure it out!

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

876

You can use the collectOffset() methods to handle all the cases, and then GreatestCommonDivisor() to calculate the GCD.

These methods save me! thanks!

901

Thanks for saying again...

908–910

Current implementation cannot read ptr array

909

Done.
(just for my understanding, I'll clarify the case for bigger load alignment in discord.

909–910

Currently

929

Do we need the LoadSize adjustment here? Can we instead iterate to ByteOffset < GVSize?

I think bound-crossing load cannot be excluded, without LoadSize.
like https://alive2.llvm.org/ce/z/jYsLBk
Sorry, I'm not confident with the semantics of this. I'll try to ask in discord.

933

Thanks! It's embarrassing...

[khei4]

refactoring

• remove LoadSize
• rename variables
• fix intermediate APInt bit size to GVSize * 8

[khei4]

now ready for review again

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

871–873

are there any better way to bitcast APInt?

929

I removed loadSize in the end

[khei4]

fix awkward indent

[khei4]

Sorry, I noticed test failed.

[khei4]

fix wrong argument

[nikic]

Extracting the stride from GEPs turned out to be trickier than I expected...

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

834

Should add a negative test using volatile.

845

This comment looks out of place, should be further down?

849

64K -> 4K

851

uint64_t

857

This is again creating a very, very wide integer :) The correct size to use here is DL.getIndexTypeSizeInBits(PtrOp->getType()) as you already do in the loop. In that case you also don't need the separate COff variable, you can let collectOffset() directly add onto this one.

859

This looks somewhat dubious -- I assume the intention here is that this is a "no-op" value for the first GreatestCommonDivisor call?

I think it would be clearer to make Stride an std::optional and then set it the first time, and use GCD for later iterations. (After the loop, if Stride is not set, it's okay to just bail out: The constant-offset case is already handled by other code, so we needn't bother with it.)

882

indeces -> indices

884

Hm, what happens if ConstOffset itself is negative? Would urem produce correct results in that case? Let's say ConstOffset = -3 and Stride = 3. Let's assume 8-bit address space to keep things simple, then ConstOffset = 253 in unsigned interpretation and 253 % 3 == 1.

Also I just realized another problem here: Just using the GCD isn't right if the GEP is not inbounds (i.e. multiplication can overflow) and the stride is not a power of two.

I believe the correct way to handle these cases is implemented in BasicAA, in particular https://github.com/llvm/llvm-project/blob/47aa1fe376a477939a1991ffe37504124af25f52/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1135-L1138 to only keep a power of two factor for non-inbounds and https://github.com/llvm/llvm-project/blob/47aa1fe376a477939a1991ffe37504124af25f52/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1168-L1170 for the final modulus.

885

A correctness check missing here is that after looking through all the GEPs, you must arrive back at GV. Otherwise there might be some kind of other operation sitting in between which preserves the underlying object, but where we can't determine the offset. As a test case, one could use a call to llvm.ptrmask for example.

894

This probably also needs to check that ConstOffset is zero? I don't think using load alignment as stride is right with a non-zero start offset.

898

It would be a bit simpler to keep using (and adding to) ConstOffset here, as we need an APInt anyway.

[nikic]

In D144445#4204759, @nikic wrote:

Extracting the stride from GEPs turned out to be trickier than I expected...

If you like, we can go back to just the alignment handling for this patch, and then add the GEP handling in a separate one on top. Either way works for me.

[khei4]

Thank you for a lot of good catches!

In D144445#4204789, @nikic wrote:

In D144445#4204759, @nikic wrote:

Extracting the stride from GEPs turned out to be trickier than I expected...

If you like, we can go back to just the alignment handling for this patch, and then add the GEP handling in a separate one on top. Either way works for me.

Sounds good to me!
Then I want to separate this into following

1. alignment-based (This revision will be)
2. (all) inbounds GEP index-based
3. non-inbounds included GEP index-based

TBH, I feel non-inbounds GEP handling is a little bit handful, but I'll read AA's implementation and try it first!

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

857

Oh... I was confused with offset and the GV byte sizes! You're right!

859

This looks somewhat dubious -- I assume the intention here is that this is a "no-op" value for the first GreatestCommonDivisor call?

Yes!

I think it would be clearer to make Stride a std::optional and then set it the first time,

Sounds reasonable, I'll use that!

884

Ah, I mistakenly assumed inbounds! Without inbounds, ConstantOffset could be negative and could overflow!

885

Good catch! I haven't known underlying-object preserved operations! I'll add tests!

894

Good catch! Yeah, we should have considered GEP-stride-based and alignment-based separately also for ConstOffset.

[khei4]

update summary and address simple fixes.

[khei4]

addresss

• ptrmasked pointer failures
• not inbounds GEP

and refactoring

• use APInt in loop
• fix BitWidth for APInt
• fix typo

[nikic]

Nearly there, I think...

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

832

Unnecessary/unusual newline.

839

getPointerOperand()` is a bit more elegant.

846

What you want to do is after the GEPOperator loop, check that the final PtrOpV is GV. This makes sure there were only GEPs.

855

"to avoid scanning too much memory" maybe -- we're not really allocating anything here.

865

This shouldn't be needed when using std::optional.

870

I don't really get what this comment is trying to say. The reason why non-inbounds GEP is tricky to handle is that there is an implicit modulo the address space size, which makes it harder to calculate the GCD.

872

You should probably extract the whole "get stride of GEP" logic into a separate function. That way, all these early bailouts don't apply for the alignment case (where we don't care about inbounds).

[khei4]

Thank you for the review! I may fuse the GEP-related plans I proposed! because I might have misunderstood non-inbounds GEP with correct alignment!

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

846

Thanks! I'll check that before and after the loop!

865

I might have missed some patterns, but I guess it's necessary because GCD (self-referencing) calculations need its initial value as the first type size. :)

Stride = APIntOps::GreatestCommonDivisor(
    Stride,
    APInt(ConstOffset.getBitWidth(), IndexTypeSize.getZExtValue()));

872

(with above comment)
Ah, OK I might misunderstand the behavior of the load with non-inbounds GEP indices, but correct alignment!

[khei4]

rebase to be only alignment-based analysis. GEP-based revision will be created.

[khei4]

make ConstOffset be not optional

[nikic]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

861

These isa checks aren't needed in this patch: For the alignment case, we don't care what the operand is.

llvm/test/Transforms/AggressiveInstCombine/patterned-load.ll

86

I don't get how this one folds with just this patch. If align 1 we have stride 1, but constarray1 needs a stride of 2, no?

[khei4]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

861

Seems like, I could not get the point of ptrmask cares! (Precisely, it seems like we need to check alignment-based and GEP-based separately for completeness) Thanks!

llvm/test/Transforms/AggressiveInstCombine/patterned-load.ll

86

Ah, sorry seems like I just forgot to commit test changes...

[khei4]

update tests, remove redundant isa check

[nikic]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

856–881

Some simplifications.

I think as far as foldPatternedLoads is concerned, we don't need the std::optional around Stride, because a Stride of 1 is always conservatively correct. It's only relevant internally while calculating GEP stride in the next patch.

857

[khei4]

apply suggestions

[khei4]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

856–881

Thanks! Yeah, simplicity for this patch matters!

[nikic]

LGTM

[khei4]

fix wrong arrow operator

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
 #include "AggressiveInstCombineInternal.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LogicCombine.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL,
   I.replaceAllUsesWith(NewOp);
 
   return true;
 }
 
 /// Reduce bitwise logic sequences.
 static bool foldBitwiseLogic(Function &F, DominatorTree &DT) {
   bool MadeChange = false;
   for (BasicBlock &BB : F) {
     // Ignore unreachable basic blocks.
     if (!DT.isReachableFromEntry(&BB))
       continue;
 
     // TODO: Combining at the function-level would allow more caching of nodes
     // which saves on compile-time, but it may hit the max value limits before
     // finding a solution. We could split the combiner based on types to make
     // the code more efficient, adjust the value of max depth/values, or use
     // APInt to support tracking more than 63 leaf values.
     LogicCombiner LC;
     for (Instruction &I : BB) {
       if (I.isBitwiseLogicOp()) {
         Value *NewV = LC.simplify(&I);
         if (NewV) {
           MadeChange = true;
           I.replaceAllUsesWith(NewV);
         }
       }
     }
   }
   return MadeChange;
 }
 
+// Return a minimum gep stride, greatest common divisor of consective gep
+// indices type sizes (c.f. Bézout's identity). Currently ignore the indices
+// constantness and struct type.
+uint64_t GetMinimumGEPStride(Value *PtrOp, const DataLayout DL) {
+
+  if (auto GEP = dyn_cast<GEPOperator>(PtrOp)) {
+    uint64_t g;
+    auto Euc = [](uint64_t a, uint64_t b) {
+      if (a < b) {
+        uint64_t t = a;
+        a = b;
+        b = t;
+      }
+      while (b != 0) {
+        uint64_t r = a % b;
+        a = b;
+        b = r;
+      }
+      return a;
+    };
+    g = DL.getTypeStoreSize(GEP->getSourceElementType());
+    Value *V = GEP;
+    while (auto GEP = dyn_cast<GEPOperator>(V)) {
+      g = Euc(g, DL.getTypeStoreSize(GEP->getResultElementType()));
+      V = GEP->getPointerOperand();
+    }
+    return g;
+  }
+
+  return 1;
+}
+
+/// If C is a constant patterned array and all valid loaded results for given
+/// alignment are same to a constant, return that constant.
+static bool foldPatternedLoads(Instruction &I, const DataLayout &DL) {
+
+  auto *LI = dyn_cast<LoadInst>(&I);
+  if (!LI)
+    return false;
+
+  // We can only fold the load if it is from a constant global with definitive
+  // initializer. Skip expensive logic if this is not the case.
+  auto *PtrOp = LI->getOperand(0);
+  auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(PtrOp));
+  if (!GV || !GV->isConstant() ||
+      (!GV->hasDefinitiveInitializer() && !GV->hasUniqueInitializer()))
+    return false;
+
+  // if Global Variable's alignment is less than load's alignment
+  // then we can't compute valid offsets.
+  uint64_t LoadAlign = LI->getAlign().value();
+  Type *LoadTy = LI->getType();
+  if (GV->getAlign().valueOrOne().value() < LoadAlign)
+    return false;
+  Constant *C = GV->getInitializer();
+
+  unsigned GVSize = DL.getTypeStoreSize(C->getType());
+  // Bail for large initializers in excess of 64K to avoid allocating
+  // too much memory.
+  if (!GVSize || 4096 < GVSize)
+    return false;
+
+  unsigned LoadSize = LoadTy->getScalarSizeInBits() / 8;
+  const APInt Offset(DL.getTypeSizeInBits(C->getType()), 0);
+  Constant *Ca = ConstantFoldLoadFromConst(
+      C, LoadTy, APInt(DL.getTypeSizeInBits(C->getType()), 0), DL);
+
+  // Any possible offset could be multiple of minimum GEP stride. And any valid
+  // offset is multiple of load alignment, so checking onle multiples of bigger
+  // one is sufficient to say results' equality.
+  uint64_t Stride = GetMinimumGEPStride(PtrOp, DL);
+  Stride = Stride < LoadAlign ? LoadAlign : Stride;
+
+  for (uint64_t ByteOffset = Stride, E = GVSize - LoadSize; ByteOffset <= E;
+       ByteOffset += Stride)
+    if (Ca != ConstantFoldLoadFromConst(
+                  C, LoadTy,
+                  APInt(DL.getTypeSizeInBits(C->getType()), ByteOffset), DL))
+      return false;
+  I.replaceAllUsesWith(Ca);
+
+  return true;
+}
+
 /// This is the entry point for folds that could be implemented in regular
 /// InstCombine, but they are separated because they are not expected to
 /// occur frequently and/or have more than a constant-length pattern match.
 static bool foldUnusualPatterns(Function &F, DominatorTree &DT,
                                 TargetTransformInfo &TTI,
                                 TargetLibraryInfo &TLI, AliasAnalysis &AA) {
   bool MadeChange = foldBitwiseLogic(F, DT);
   for (BasicBlock &BB : F) {
for (BasicBlock &BB : F) {
     // iteratively in this loop rather than waiting until the end.
     for (Instruction &I : make_early_inc_range(llvm::reverse(BB))) {
       MadeChange |= foldAnyOrAllBitsSet(I);
       MadeChange |= foldGuardedFunnelShift(I, DT);
       MadeChange |= tryToRecognizePopCount(I);
       MadeChange |= tryToFPToSat(I, TTI);
       MadeChange |= tryToRecognizeTableBasedCttz(I);
       MadeChange |= foldConsecutiveLoads(I, DL, TTI, AA);
+      MadeChange |= foldPatternedLoads(I, DL);
       // NOTE: This function introduces erasing of the instruction `I`, so it
       // needs to be called at the end of this sequence, otherwise we may make
       // bugs.
       MadeChange |= foldSqrt(I, TTI, TLI);
     }
   }
 
   // We're done with transforms, so remove dead instructions.

llvm/test/Transforms/AggressiveInstCombine/patterned-load.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=aggressive-instcombine -S -data-layout="e" | FileCheck %s --check-prefixes=CHECK,LE
+; RUN: opt < %s -passes=aggressive-instcombine -S -data-layout="E" | FileCheck %s --check-prefixes=CHECK,BE
+
+@constarray = internal constant [8 x i8]  c"\01\00\01\00\01\00\01\00", align 4
+@constpackedstruct = internal constant <{[8 x i8]}>  <{[8 x i8] c"\01\00\01\00\01\00\01\00"}>, align 4
+
+define i8 @gep_load_i8_align2(i64 %idx){
+; CHECK-LABEL: @gep_load_i8_align2(
+; CHECK-NEXT:    ret i8 1
+;
+  %1 = getelementptr inbounds i8, ptr @constarray, i64 %idx
+  %2 = load i8, ptr %1, align 2
+  ret i8 %2
+}
+
+; can't be folded
+define i8 @gep_load_i8_align1(i64 %idx){
+; CHECK-LABEL: @gep_load_i8_align1(
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, ptr @constarray, i64 [[IDX:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i8, ptr [[TMP1]], align 1
+; CHECK-NEXT:    ret i8 [[TMP2]]
+;
+  %1 = getelementptr inbounds i8, ptr @constarray, i64 %idx
+  %2 = load i8, ptr %1, align 1
+  ret i8 %2
+}
+
+define i32 @gep_i32_load_i32_align4(i64 %idx){
+; LE-LABEL: @gep_i32_load_i32_align4(
+; LE-NEXT:    ret i32 65537
+;
+; BE-LABEL: @gep_i32_load_i32_align4(
+; BE-NEXT:    ret i32 16777472
+;
+  %1 = getelementptr inbounds i32, ptr @constarray, i64 %idx
+  %2 = load i32, ptr %1, align 4
+  ret i32 %2
+}
+
+define i32 @gep_i32_load_i32_align4_packedstruct(i64 %idx){
+; LE-LABEL: @gep_i32_load_i32_align4_packedstruct(
+; LE-NEXT:    ret i32 65537
+;
+; BE-LABEL: @gep_i32_load_i32_align4_packedstruct(
+; BE-NEXT:    ret i32 16777472
+;
+  %1 = getelementptr inbounds i32, ptr @constpackedstruct, i64 %idx
+  %2 = load i32, ptr %1, align 4
+  ret i32 %2
+}
+
+; can't be folded
+define i32 @gep_i8_load_i32_align1(i64 %idx){
+; CHECK-LABEL: @gep_i8_load_i32_align1(
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, ptr @constarray, i64 [[IDX:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[TMP1]], align 1
+; CHECK-NEXT:    ret i32 [[TMP2]]
+;
+  %1 = getelementptr inbounds i8, ptr @constarray, i64 %idx
+  %2 = load i32, ptr %1, align 1
+  ret i32 %2
+}
+
+; can't be folded
+define i32 @gep_i8_load_i32_align1_packedstruct(i64 %idx){
+; CHECK-LABEL: @gep_i8_load_i32_align1_packedstruct(
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, ptr @constpackedstruct, i64 [[IDX:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[TMP1]], align 1
+; CHECK-NEXT:    ret i32 [[TMP2]]
+;
+  %1 = getelementptr inbounds i8, ptr @constpackedstruct, i64 %idx
+  %2 = load i32, ptr %1, align 1
+  ret i32 %2
+}
+
+define i32 @gep_i16_load_i32_align1(i64 %idx){
+; LE-LABEL: @gep_i16_load_i32_align1(
+; LE-NEXT:    ret i32 65537
+;
+; BE-LABEL: @gep_i16_load_i32_align1(
+; BE-NEXT:    ret i32 16777472
+;
+  %1 = getelementptr inbounds i16, ptr @constarray, i64 %idx
+  %2 = load i32, ptr %1, align 1
+  ret i32 %2
+}

llvm/test/Transforms/InstSimplify/load-patterned-aggregates.ll

-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
-target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32"
-@constzeroarray = internal constant [4 x i32] zeroinitializer
-
-@constarray = internal constant [8 x i8]  c"\01\00\01\00\01\00\01\00", align 4
-@conststruct = internal constant <{[8 x i8]}>  <{[8 x i8] c"\01\00\01\00\01\00\01\00"}>, align 4
-
-define i32 @load_gep_const_zero_array(i64 %idx) {
-; CHECK-LABEL: @load_gep_const_zero_array(
-; CHECK-NEXT:    ret i32 0
-;
-  %gep = getelementptr inbounds [4 x i32], ptr @constzeroarray, i64 0, i64 %idx
-  %load = load i32, ptr %gep
-  ret i32 %load
-}
-
-define i8 @load_i8_multi_gep_const_zero_array(i64 %idx1, i64 %idx2) {
-; CHECK-LABEL: @load_i8_multi_gep_const_zero_array(
-; CHECK-NEXT:    ret i8 0
-;
-  %gep1 = getelementptr inbounds i8, ptr @constzeroarray, i64 %idx1
-  %gep = getelementptr inbounds i8, ptr %gep1, i64 %idx2
-  %load = load i8, ptr %gep
-  ret i8 %load
-}
-
-
-define i32 @load_gep_const_patterned_array(i64 %idx) {
-; CHECK-LABEL: @load_gep_const_patterned_array(
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @constarray, i64 0, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[GEP]], align 4
-; CHECK-NEXT:    ret i32 [[LOAD]]
-;
-  %gep = getelementptr inbounds [4 x i32], ptr @constarray, i64 0, i64 %idx
-  %load = load i32, ptr %gep
-  ret i32 %load
-}
-
-define i8 @load_i8_multi_gep_const_array(i64 %idx1, i64 %idx2) {
-; CHECK-LABEL: @load_i8_multi_gep_const_array(
-; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds i8, ptr @constarray, i64 [[IDX1:%.*]]
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, ptr [[GEP1]], i64 [[IDX2:%.*]]
-; CHECK-NEXT:    [[LOAD:%.*]] = load i8, ptr [[GEP]], align 1
-; CHECK-NEXT:    ret i8 [[LOAD]]
-;
-  %gep1 = getelementptr inbounds i8, ptr @constarray, i64 %idx1
-  %gep = getelementptr inbounds i8, ptr %gep1, i64 %idx2
-  %load = load i8, ptr %gep
-  ret i8 %load
-}
-
-; TODO: this should be ret i8 1
-define i8 @gep_load_i8_align2(i64 %idx){
-; CHECK-LABEL: @gep_load_i8_align2(
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, ptr @constarray, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = load i8, ptr [[TMP1]], align 2
-; CHECK-NEXT:    ret i8 [[TMP2]]
-;
-  %1 = getelementptr inbounds i8, ptr @constarray, i64 %idx
-  %2 = load i8, ptr %1, align 2
-  ret i8 %2
-}
-
-; can't be folded
-define i8 @gep_load_i8_align1(i64 %idx){
-; CHECK-LABEL: @gep_load_i8_align1(
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, ptr @constarray, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = load i8, ptr [[TMP1]], align 1
-; CHECK-NEXT:    ret i8 [[TMP2]]
-;
-  %1 = getelementptr inbounds i8, ptr @constarray, i64 %idx
-  %2 = load i8, ptr %1, align 1
-  ret i8 %2
-}
-
-; TODO: this should be ret i8 65537 on the case for little endian
-define i32 @gep_i32_load_i32_align4(i64 %idx){
-; CHECK-LABEL: @gep_i32_load_i32_align4(
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i32, ptr @constarray, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[TMP1]], align 4
-; CHECK-NEXT:    ret i32 [[TMP2]]
-;
-  %1 = getelementptr inbounds i32, ptr @constarray, i64 %idx
-  %2 = load i32, ptr %1, align 4
-  ret i32 %2
-}
-
-; TODO: this should be ret i8 65537 on the case for little endian
-define i32 @gep_i32_load_i32_align4_struct(i64 %idx){
-; CHECK-LABEL: @gep_i32_load_i32_align4_struct(
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i32, ptr @conststruct, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[TMP1]], align 4
-; CHECK-NEXT:    ret i32 [[TMP2]]
-;
-  %1 = getelementptr inbounds i32, ptr @conststruct, i64 %idx
-  %2 = load i32, ptr %1, align 4
-  ret i32 %2
-}
-
-; can't be folded
-define i32 @gep_i8_load_i32_align1(i64 %idx){
-; CHECK-LABEL: @gep_i8_load_i32_align1(
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, ptr @constarray, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[TMP1]], align 1
-; CHECK-NEXT:    ret i32 [[TMP2]]
-;
-  %1 = getelementptr inbounds i8, ptr @constarray, i64 %idx
-  %2 = load i32, ptr %1, align 1
-  ret i32 %2
-}
-
-; can't be folded
-define i32 @gep_i8_load_i32_align1_struct(i64 %idx){
-; CHECK-LABEL: @gep_i8_load_i32_align1_struct(
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, ptr @conststruct, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[TMP1]], align 1
-; CHECK-NEXT:    ret i32 [[TMP2]]
-;
-  %1 = getelementptr inbounds i8, ptr @conststruct, i64 %idx
-  %2 = load i32, ptr %1, align 1
-  ret i32 %2
-}
-; TODO: This could be folded but need to see GEP source types
-define i32 @gep_i16_load_i32_align1(i64 %idx){
-; CHECK-LABEL: @gep_i16_load_i32_align1(
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr @constarray, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[TMP1]], align 1
-; CHECK-NEXT:    ret i32 [[TMP2]]
-;
-  %1 = getelementptr inbounds i16, ptr @constarray, i64 %idx
-  %2 = load i32, ptr %1, align 1
-  ret i32 %2
-}

llvm/test/Transforms/InstSimplify/load.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
 
 @zeroinit = constant {} zeroinitializer
 @poison = constant {} poison
+@constzeroarray = internal constant [4 x i32] zeroinitializer
 
 define i32 @crash_on_zeroinit() {
 ; CHECK-LABEL: @crash_on_zeroinit(
 ; CHECK-NEXT:    ret i32 poison
 ;
   %load = load i32, ptr @zeroinit
   ret i32 %load
 }

 ; This does an out of bounds load from the global constant
 define <3 x float> @load_vec3() {
 ; CHECK-LABEL: @load_vec3(
 ; CHECK-NEXT:    ret <3 x float> poison
 ;
   %1 = load <3 x float>, ptr getelementptr inbounds (<3 x float>, ptr @constvec, i64 1)
   ret <3 x float> %1
 }
+
+define i32 @load_gep_const_zero_array(i64 %idx) {
+; CHECK-LABEL: @load_gep_const_zero_array(
+; CHECK-NEXT:    ret i32 0
+;
+  %gep = getelementptr inbounds [4 x i32], ptr @constzeroarray, i64 0, i64 %idx
+  %load = load i32, ptr %gep
+  ret i32 %load
+}
+
+define i8 @load_i8_multi_gep_const_zero_array(i64 %idx1, i64 %idx2) {
+; CHECK-LABEL: @load_i8_multi_gep_const_zero_array(
+; CHECK-NEXT:    ret i8 0
+;
+  %gep1 = getelementptr inbounds i8, ptr @constzeroarray, i64 %idx1
+  %gep = getelementptr inbounds i8, ptr %gep1, i64 %idx2
+  %load = load i8, ptr %gep
+  ret i8 %load
+}

llvm/test/Transforms/PhaseOrdering/X86/nancvt.ll

 @var = external global i32
 
 ; SNAN becomes QNAN on fptrunc:
 ; 2147228864 = 0x7ffc1cc0 : QNAN
 
 define i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store volatile i32 2147027116, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 -1610612736, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 2147027116, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 -2147483648, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 2147027116, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 -1073741824, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
 ; CHECK-NEXT:    store volatile i32 2147228864, ptr @var, align 4
 ; CHECK-NEXT:    store volatile i32 2147228864, ptr @var, align 4
 ; CHECK-NEXT:    store volatile i32 2147228864, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 2147027116, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 -1610612736, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 2147027116, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 -2147483648, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 2147027116, ptr @var, align 4
-; CHECK-NEXT:    store volatile i32 -1073741824, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
+; CHECK-NEXT:    store volatile i32 poison, ptr @var, align 4
 ; CHECK-NEXT:    store volatile i32 2147228864, ptr @var, align 4
 ; CHECK-NEXT:    store volatile i32 2147228864, ptr @var, align 4
 ; CHECK-NEXT:    store volatile i32 2147228864, ptr @var, align 4
 ; CHECK-NEXT:    ret i32 undef
 ;
 entry:
   %retval = alloca i32, align 4
   %i = alloca i32, align 4