LSR tunings for SystemZ, with some minor common code changes

[jonpa]

Summary

The purpose of this patch is to make LSR generate better code for SystemZ in the cases of memory intrinsics and comparison of immediate with memory. These instructions in particular can have no index register and can only accept a small immediate offset. Improvements on benchmarks have been confirmed.

In order to achieve this, the following common code changes were made:

• New TTI hook: LSRWithInstrQueries(), which defaults to false. Controls if LSR should do instruction-based addressing evaluations by calling isLegalAddressingMode() and isFoldableMemAccessOffset() with the Instruction pointers.
• isLegalAddressingMode() gets a new optional Instruction* parameter (defaults to nullptr) used by LSR if Target returns true in LSRWithInstrQueries(). All target methods have been updated as well.
• In LSR / isAddressUse(): handle address operands of memset, memmove and memcpy as address uses.
• In LSR / RateFormula(): Don't add to ImmCost if the instructions are already checked. It only adds confusion when the results are otherwise equal. Call isFoldableMemAccessOffset() for any LSRUse::Address, not just loads / stores.
• In LSR / isAMCompletelyFolded(): Let target look at instructions if it returns true in LSRWithInstrQueries().
  
  SystemZ:
• isLSRCostLess() overriden to check instruction counts like X86 does it.
• isLegalAddressingMode() and isFoldableMemAccessOffset() improved to handle memcpy and compare imm w/ mem.
• LSRWithInstrQueries() returns true
• minor updates of tests dag-combine-01.ll and loop-01.ll
• Two new tests in loop-01.ll

[qcolombet]

Hi Jonas,

Unless I am mistaken, I see three different changes here.
First batch is

• • New TTI hook: LSRWithInstrQueries(), which defaults to false. Controls if LSR should do instruction-based addressing evaluations by calling isLegalAddressingMode() and isFoldableMemAccessOffset() with the Instruction pointers.
• isLegalAddressingMode() gets a new optional Instruction* parameter (defaults to nullptr) used by LSR if Target returns true in LSRWithInstrQueries(). All target methods have been updated as well.
  • In LSR / isAMCompletelyFolded(): Let target look at instructions if it returns true in LSRWithInstrQueries().

Second batch is

• In LSR / isAddressUse(): handle address operands of memset, memmove and memcpy as address uses.

Third batch is

• In LSR / RateFormula(): Don't add to ImmCost if the instructions are already checked. It only adds confusion when the results are otherwise equal. Call isFoldableMemAccessOffset() for any LSRUse::Address, not just loads / stores.

Could you please split the patch accordingly?

More comments inlined.

Cheers,
-Quentin

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1657

I feel that this code does not belong here.

Indeed, we have quite a few isAMCompletelyFolded overloaded functions, and I believe not all invocations would go through that specific instance.
Instead, I would have expected this to happen to the lower most version of the isAMCompletelyFolded version. The one that calls isLegalAddressingMode.

test/CodeGen/SystemZ/loop-01.ll

243

Could you run opt -instnamer on the IR?

[jonpa]

Test updated with opt -instnamer per request.

[jonpa]

I broke out "second batch" (isAddressUse()) into https://reviews.llvm.org/D35262

I however think 1 & 3 both depend on LSRWithInstrQueries(), so I let them remain here together, if that's ok?

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1657

The reason that I put it here, is because this is where LU is available. The check can't be done without LU (which has the Fixups), so if it's not placed here, the argument lists of the other versions must be changed, as well as the call sites of it and isLegalUse() (and possibly more?) to make the Fixups available. Is this what you have in mind, and if so should LU replace the other LU-arguments like MinOffset etc?

test/CodeGen/SystemZ/loop-01.ll

243

done.

[qcolombet]

I see why second batch depends on this patch. I wonder if it should though.
Hence, do we rely guard that check with LSRWithInstrQueries?

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1282

Why would we guard that check with TTI.LSRWithInstrQueries, whereas it was guarded previously.

1286

This slightly changes how/when we accumulate ImmCost.
Is that intentional?

1657

The thing that I don't like is that what we're basically copying what's inside the bottom most version of isAMCompletelyFolded in the Address case. If possible I would have liked we call that code.

Could we keep that loop here but call the bottom most isAMCompletelyFolded with an additional Instr parameter?

[jonpa]

Call isAMCompletelyFolded() with Instr parameter instead of duplicating code.

[jonpa]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1282

The idea here is that ImmCost is not updated with Offset when Target checks it for each fixup in isFoldableMemAccessOffset(). I had found loop regressions where the NumBaseAdds were the same, but ImmCost were different, and I found that this would be resolved by not updating ImmCost with Offset. I am not sure exactly why -- my guess is that the better formulas (including pre-LSR/input) go first.

1286

yes -- SA

1657

yes - that works just the same.

[qcolombet]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1282

Two things regarding this comment:

• 1. ---

The idea was that if NumBaseAdds is the same, ImmCost is used as a tie breaker.
If I understand correctly you're saying not using this as a tie breaker generates better code. I found that concerning.

Could you dig into that before moving forward?

Assuming you're guess is correct, we should document that fact and make sure the order in the list is not pure luck.

• 2. ---

This does not answer the question why we should guard this check with LSRWithInstrQueries given it wasn't guarded previously. My concern here is that we change a fairly high weighted piece of the formulae rating and given all other target would return false for LSRWithInstrQueries, I am afraid it will affect their performance across the board.

[jonpa]

The idea was that if NumBaseAdds is the same, ImmCost is used as a tie breaker.
If I understand correctly you're saying not using this as a tie breaker generates better code. I found that concerning.

Could you dig into that before moving forward?

1. If I move back one step and update the ImmCost like

    if (LU.Kind == LSRUse::Address && TTI.LSRWithInstrQueries()) {
       if (!TTI.isFoldableMemAccessOffset(Fixup.UserInst, Offset))
         C.NumBaseAdds++;
-    } else
-      C.ImmCost += APInt(64, Offset, true).getMinSignedBits();
+    }
+
+    C.ImmCost += APInt(64, Offset, true).getMinSignedBits();
   }

I get that on SPEC-2006, now 717 loops are bigger (as expected), while 361 are smaller. So this affects only ~2% of the loops.

Without ImmCost on address fixups:
717 loops better

205 better because live-out PHI duplicated and modified slightly in other version  (#0)
177 better because of more spilling in other version (#1)
280 better because more COPYs in other version (#2)
132 better becasue less loads of constants in loops (#3)
 56 better because of less immediate adds
    42 before a compare using same IV (#4)
    14 before a memory instruction
 83 better because more fused compare / branches (#5)
--- left:
 (27 loops better)

With ImmCost on address fixups:
361 loops better

  5 better because live-out PHI duplicated and modified slightly in other version   (#0)
173 better because of more spilling in other version (#1)
165 better because more COPYs in other version (#2)
 25 better becasue less loads of constants in loops (#3)
 99 better because of less immediate adds
    89 before a compare using same IV (#4)
    10 before a memory instruction
 26 better because more fused compare / branches (#5)
--- left:
 (22 loops better)

#0: It seems that LSR is not aware if a live-out PHI is reused or not. The formula that reuses a live-out phi does not need the extra phi, which should mean a cost difference of one add in the loop. So if LSR comes up with a formula that offsets the original PHI with some offset which makes the total Offset bits of the fixups less, it will insert a new phi.

Since this is clearly bad (205/5), my guess is that LSR most of the time manages to first use an existing PHI. Without the fixups ImmCost, the formulas have the same cost, and the formula with the original PHI remains.

#1: These loops got randomly different number of spills / reloads in them. This is a current regalloc flaw, and there is a patch in progress to handle it by Wei Mi (https://bugs.llvm.org/show_bug.cgi?id=32722). This happens evenly (177/173) w/ or w/out ImmCost, so this isn't an LSR issue.

#2: The coalescing isn't perfect, and I have for instance seen cases where due to the pre-RA-scheduler the IV increment may be scheduled above the last use of it, prohibiting coalescing of the IV. As a result, there is an extra needless copy after the IV increment. Not sure why there are more COPYs with ImmCost.

#3: Not sure why, but it seems that a lot less loads of constants got hoisted out of loops with ImmCost. Maybe different register allocation for some reason?

#4: It seems that ImmCost did reduce the number of adds of immediates before compares somewhat (42/89).

#5: A few more compares got fused into the branch without ImmCost (83/26)

So, there are maybe a thing or two here possible to improve, but I am not sure if these details affect more than the 2% of the loops or not...

I think for SystemZ, a first step might be to just skip the ImmCost in the cost function, since that actually only affects 18 loops, so that is surely an easier way if this patch cannot be accepted as is. In that case, I would revert the LoopStrenghtReduce patch changes related to ImmCost.

This does not answer the question why we should guard this check with LSRWithInstrQueries given it wasn't guarded previously. My concern here is that we change a fairly high weighted piece of the formulae rating and given all other target would return false for LSRWithInstrQueries, I am afraid it will affect their performance across the board.

I was just seing that only SystemZ is using isFoldableMemAccessOffset(), but I suppose there are out-of-tree targets that you are concerned about?

[jonpa]

Patch updated so that SystemZ drops ImmCost from its implementation of isLSRCostLess() since this simplifies the common code changes and has nearly no impact at all.

[jonpa]

Sorry - missed a comment that needed updating.

[uweigand]

A few comments/questions, looking only at the SystemZ-specific parts.

I'm now wondering what the difference between isLegalAddressingMode and isFoldableMemAccessOffset is, now that they both take a specific instruction. Don't these two functions now answer the exact same question? And if so, shouldn't the implementation then be merged? The following questions about differences between the two would be moot if we actually had a shared implementation here.

For example, you change isLegalAddressingMode to check for hasNoIndexReg, but not needsD12. If the function does get an Instruction, and we can see that it won't accept large displacements, shouldn't we then reject the address from isLegalAddressingMode as well?

Also, the various checks for float/vector access in isFoldableMemAccessOffset -- shouldn't they move to hasLessAddressing? We know that float/vector accesses won't accept large displacements, so shouldn't the function say so?

The comment before hasLessAddressing talks about accesses being converted to vector instructions, but that happens only on z13 or later. Shouldn't this then be guarded by a Subtarget feature check just like the existing code in isFoldableMemAccessOffset does?

Finally, I'm not really happy about the names ... hasLessAddressing sound a bit strange. Maybe instead a function called "supportedAddressingMode" that takes an Instruction and returns a description of the addressing mode (long vs. short displacement, index vs. no index), either as an enum or as a pair of booleans,

[qcolombet]

Hi Jonas,

Thanks for digging into the regressions.

The patch makes sense now.

#0: It seems that LSR is not aware if a live-out PHI is reused or not. The formula that reuses a live-out phi does not need the extra phi, which should mean a cost difference of one add in the loop. So if LSR comes up with a formula that offsets the original PHI with some offset which makes the total Offset bits of the fixups less, it will insert a new phi.

Since this is clearly bad (205/5), my guess is that LSR most of the time manages to first use an existing PHI. Without the fixups ImmCost, the formulas have the same cost, and the formula with the original PHI remains.

That sounds sensible, we should improve that in a different patch.

Cheers,
-Quentin

[qcolombet]

BTW, my review does not include SystemZ changes ;)

[jonpa]

SystemZ part updated per review.

I'm now wondering what the difference between isLegalAddressingMode and isFoldableMemAccessOffset is, now that they both take a specific instruction. Don't these two functions now answer the exact same question? And if so, shouldn't the implementation then be merged? The following questions about differences between the two would be moot if we actually had a shared implementation here.

I agree this isn't perfect. I also noticed this before, and thought this could be possibly refactored but however also noticed the many different overloaded versions of isLegalAddressingMode() and thought that it could wait as a next step, perhaps. RateFormula() currently only checks the fixup instructions for the offsets, so I am not sure this is a trivial change.

For example, you change isLegalAddressingMode to check for hasNoIndexReg, but not needsD12. If the function does get an Instruction, and we can see that it won't accept large displacements, shouldn't we then reject the address from isLegalAddressingMode as well?

Makes sense -- see below.

Also, the various checks for float/vector access in isFoldableMemAccessOffset -- shouldn't they move to hasLessAddressing? We know that float/vector accesses won't accept large displacements, so shouldn't the function say so?

Done.

The comment before hasLessAddressing talks about accesses being converted to vector instructions, but that happens only on z13 or later. Shouldn't this then be guarded by a Subtarget feature check just like the existing code in isFoldableMemAccessOffset does?

Good point - fixed.

Finally, I'm not really happy about the names ... hasLessAddressing sound a bit strange. Maybe instead a function called "supportedAddressingMode" that takes an Instruction and returns a description of the addressing mode (long vs. short displacement, index vs. no index), either as an enum or as a pair of booleans.

Changed it and agree this is more clear by returning both values as a pair. Does it look acceptable now?

I see then two points that could be handled in separate patches:

• Model the cost of live-out PHIs. I actually see now that this is supposed to be handled with isExistingPhi(), but I guess could always try to look further why it appeared to not always work for me.
• Try if possible to merge isLegalAddressingMode() with isFoldableMemAccessOffset() and also improve isLegalAddressingMode() to check the offset. I have inserted a TODO comment so that we remember this.

[uweigand]

I agree this isn't perfect. I also noticed this before, and thought this could be possibly refactored but however also noticed the many different overloaded versions of isLegalAddressingMode() and thought that it could wait as a next step, perhaps. RateFormula() currently only checks the fixup instructions for the offsets, so I am not sure this is a trivial change.

Right, changing the whole common code interface would be a larger effort. I was primarily concerned about the SystemZ implementation of those routines -- they should be doing the same thing, ideally by sharing code. However, with this latest version of the patch, they actually already do share most of the code, so my concern is mostly resolved. If we can go on and unify the offset checks (i.e. have the same 12- or 20-bit checks in both routines), then we should be completely OK.

I understand this change might lead to changes in generated code, which might have other performance impacts. So I'd be fine with checking in this patch, and then following up with another patch to fix the offset checks (after doing another round of benchmarking).

Changed it and agree this is more clear by returning both values as a pair. Does it look acceptable now?

Yes, this does indeed look much better now.

The SystemZ changes overall LGTM now, just some minor in-line comments.

lib/Target/SystemZ/SystemZISelLowering.cpp

588

Just as a minor readability enhancement, I'd move the supportedAddressingMode check down here, and write the whole thing like this:

if (I != nullptr && !supportedAddressingMode(I, Subtarget.hasVector()).IndexReg)
  // No indexing allowed.
  return AM.Scale == 0;
else
  // Indexing is OK but no scale factor can be applied.
  return AM.Scale == 0 || AM.Scale == 1;

623

Typo: displacement

633

Hmm. I know the code didn't before either, but shouldn't we check whether the Offset fits into 20 bits here? Maybe at least add a TODO if we don't want to change it right now.

[jonpa]

Thanks for review!
r308729

lib/Target/SystemZ/SystemZISelLowering.cpp

588

Done.

633

I think my idea was that isLegalAddressingMode() would handle that during formula generation. I anyhow added a TODO and will check this for the next patch.

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// against the immediate without having to materialize the immediate into a
   /// register.
   bool isLegalICmpImmediate(int64_t Imm) const;
 
   /// \brief Return true if the addressing mode represented by AM is legal for
   /// this target, for a load/store of the specified type.
   /// The type may be VoidTy, in which case only return true if the addressing
   /// mode is legal for a load/store of any legal type.
+  /// If target returns true in LSRWithInstrQueries(), I may be valid.
   /// TODO: Handle pre/postinc as well.
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                              bool HasBaseReg, int64_t Scale,
-                             unsigned AddrSpace = 0) const;
+                             unsigned AddrSpace = 0,
+                             Instruction *I = nullptr) const;
 
   /// \brief Return true if LSR cost of C1 is lower than C1.
   bool isLSRCostLess(TargetTransformInfo::LSRCost &C1,
                      TargetTransformInfo::LSRCost &C2) const;
 
   /// \brief Return true if the target supports masked load/store
   /// AVX2 and AVX-512 targets allow masks for consecutive load and store
   bool isLegalMaskedStore(Type *DataType) const;
public:
   /// of the specified type.
   /// If the AM is supported, the return value must be >= 0.
   /// If the AM is not supported, it returns a negative value.
   /// TODO: Handle pre/postinc as well.
   int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                            bool HasBaseReg, int64_t Scale,
                            unsigned AddrSpace = 0) const;
 
+  /// \brief Return true if the loop strength reduce pass should make
+  /// Instruction* based TTI queries to isFoldableMemAccessOffset() and
+  /// isLegalAddressingMode(). This is needed on SystemZ, where e.g. a memcpy
+  /// can only have a 12 bit unsigned immediate offset and no index register.
+  bool LSRWithInstrQueries() const;
+
   /// \brief Return true if target supports the load / store
   /// instruction with the given Offset on the form reg + Offset. It
   /// may be that Offset is too big for a certain type (register
   /// class).
   bool isFoldableMemAccessOffset(Instruction *I, int64_t Offset) const;
   
   /// \brief Return true if it's free to truncate a value of type Ty1 to type
   /// Ty2. e.g. On x86 it's free to truncate a i32 value in register EAX to i16
public:
   virtual unsigned getFlatAddressSpace() = 0;
   virtual bool isLoweredToCall(const Function *F) = 0;
   virtual void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) = 0;
   virtual bool isLegalAddImmediate(int64_t Imm) = 0;
   virtual bool isLegalICmpImmediate(int64_t Imm) = 0;
   virtual bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV,
                                      int64_t BaseOffset, bool HasBaseReg,
                                      int64_t Scale,
-                                     unsigned AddrSpace) = 0;
+                                     unsigned AddrSpace,
+                                     Instruction *I) = 0;
   virtual bool isLSRCostLess(TargetTransformInfo::LSRCost &C1,
                              TargetTransformInfo::LSRCost &C2) = 0;
   virtual bool isLegalMaskedStore(Type *DataType) = 0;
   virtual bool isLegalMaskedLoad(Type *DataType) = 0;
   virtual bool isLegalMaskedScatter(Type *DataType) = 0;
   virtual bool isLegalMaskedGather(Type *DataType) = 0;
   virtual bool prefersVectorizedAddressing() = 0;
   virtual int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                    int64_t BaseOffset, bool HasBaseReg,
                                    int64_t Scale, unsigned AddrSpace) = 0;
+  virtual bool LSRWithInstrQueries() = 0;
   virtual bool isFoldableMemAccessOffset(Instruction *I, int64_t Offset) = 0;
   virtual bool isTruncateFree(Type *Ty1, Type *Ty2) = 0;
   virtual bool isProfitableToHoist(Instruction *I) = 0;
   virtual bool isTypeLegal(Type *Ty) = 0;
   virtual unsigned getJumpBufAlignment() = 0;
   virtual unsigned getJumpBufSize() = 0;
   virtual bool shouldBuildLookupTables() = 0;
   virtual bool shouldBuildLookupTablesForConstant(Constant *C) = 0;
public:
   bool isLegalAddImmediate(int64_t Imm) override {
     return Impl.isLegalAddImmediate(Imm);
   }
   bool isLegalICmpImmediate(int64_t Imm) override {
     return Impl.isLegalICmpImmediate(Imm);
   }
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                              bool HasBaseReg, int64_t Scale,
-                             unsigned AddrSpace) override {
+                             unsigned AddrSpace,
+                             Instruction *I) override {
     return Impl.isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg,
-                                      Scale, AddrSpace);
+                                      Scale, AddrSpace, I);
   }
   bool isLSRCostLess(TargetTransformInfo::LSRCost &C1,
                      TargetTransformInfo::LSRCost &C2) override {
     return Impl.isLSRCostLess(C1, C2);
   }
   bool isLegalMaskedStore(Type *DataType) override {
     return Impl.isLegalMaskedStore(DataType);
   }
bool prefersVectorizedAddressing() override {
     return Impl.prefersVectorizedAddressing();
   }
   int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                            bool HasBaseReg, int64_t Scale,
                            unsigned AddrSpace) override {
     return Impl.getScalingFactorCost(Ty, BaseGV, BaseOffset, HasBaseReg,
                                      Scale, AddrSpace);
   }
+  bool LSRWithInstrQueries() override {
+    return Impl.LSRWithInstrQueries();
+  }
   bool isFoldableMemAccessOffset(Instruction *I, int64_t Offset) override {
     return Impl.isFoldableMemAccessOffset(I, Offset);
   }
   bool isTruncateFree(Type *Ty1, Type *Ty2) override {
     return Impl.isTruncateFree(Ty1, Ty2);
   }
   bool isProfitableToHoist(Instruction *I) override {
     return Impl.isProfitableToHoist(I);

include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   void getUnrollingPreferences(Loop *, TTI::UnrollingPreferences &) {}
 
   bool isLegalAddImmediate(int64_t Imm) { return false; }
 
   bool isLegalICmpImmediate(int64_t Imm) { return false; }
 
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                              bool HasBaseReg, int64_t Scale,
-                             unsigned AddrSpace) {
+                             unsigned AddrSpace, Instruction *I = nullptr) {
     // Guess that only reg and reg+reg addressing is allowed. This heuristic is
     // taken from the implementation of LSR.
     return !BaseGV && BaseOffset == 0 && (Scale == 0 || Scale == 1);
   }
 
   bool isLSRCostLess(TTI::LSRCost &C1, TTI::LSRCost &C2) {
     return std::tie(C1.NumRegs, C1.AddRecCost, C1.NumIVMuls, C1.NumBaseAdds,
                     C1.ScaleCost, C1.ImmCost, C1.SetupCost) <
int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                            bool HasBaseReg, int64_t Scale, unsigned AddrSpace) {
     // Guess that all legal addressing mode are free.
     if (isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg,
                               Scale, AddrSpace))
       return 0;
     return -1;
   }
 
+  bool LSRWithInstrQueries() { return false; }
+
   bool isFoldableMemAccessOffset(Instruction *I, int64_t Offset) { return true; }
 
   bool isTruncateFree(Type *Ty1, Type *Ty2) { return false; }
 
   bool isProfitableToHoist(Instruction *I) { return true; }
 
   bool isTypeLegal(Type *Ty) { return false; }
 

include/llvm/CodeGen/BasicTTIImpl.h

public:
   }
 
   bool isLegalICmpImmediate(int64_t imm) {
     return getTLI()->isLegalICmpImmediate(imm);
   }
 
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                              bool HasBaseReg, int64_t Scale,
-                             unsigned AddrSpace) {
+                             unsigned AddrSpace, Instruction *I = nullptr) {
     TargetLoweringBase::AddrMode AM;
     AM.BaseGV = BaseGV;
     AM.BaseOffs = BaseOffset;
     AM.HasBaseReg = HasBaseReg;
     AM.Scale = Scale;
-    return getTLI()->isLegalAddressingMode(DL, AM, Ty, AddrSpace);
+    return getTLI()->isLegalAddressingMode(DL, AM, Ty, AddrSpace, I);
   }
 
   bool isLSRCostLess(TTI::LSRCost C1, TTI::LSRCost C2) {
     return TargetTransformInfoImplBase::isLSRCostLess(C1, C2);
   }
 
   int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                            bool HasBaseReg, int64_t Scale, unsigned AddrSpace) {

include/llvm/Target/TargetLowering.h

public:
   /// The type may be VoidTy, in which case only return true if the addressing
   /// mode is legal for a load/store of any legal type.  TODO: Handle
   /// pre/postinc as well.
   ///
   /// If the address space cannot be determined, it will be -1.
   ///
   /// TODO: Remove default argument
   virtual bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM,
-                                     Type *Ty, unsigned AddrSpace) const;
+                                     Type *Ty, unsigned AddrSpace,
+                                     Instruction *I = nullptr) const;
 
   /// \brief Return the cost of the scaling factor used in the addressing mode
   /// represented by AM for this target, for a load/store of the specified type.
   ///
   /// If the AM is supported, the return value must be >= 0.
   /// If the AM is not supported, it returns a negative value.
   /// TODO: Handle pre/postinc as well.
   /// TODO: Remove default argument

lib/Analysis/TargetTransformInfo.cpp

 bool TargetTransformInfo::isLegalICmpImmediate(int64_t Imm) const {
   return TTIImpl->isLegalICmpImmediate(Imm);
 }
 
 bool TargetTransformInfo::isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV,
                                                 int64_t BaseOffset,
                                                 bool HasBaseReg,
                                                 int64_t Scale,
-                                                unsigned AddrSpace) const {
+                                                unsigned AddrSpace,
+                                                Instruction *I) const {
   return TTIImpl->isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg,
-                                        Scale, AddrSpace);
+                                        Scale, AddrSpace, I);
 }
 
 bool TargetTransformInfo::isLSRCostLess(LSRCost &C1, LSRCost &C2) const {
   return TTIImpl->isLSRCostLess(C1, C2);
 }
 
 bool TargetTransformInfo::isLegalMaskedStore(Type *DataType) const {
   return TTIImpl->isLegalMaskedStore(DataType);
int TargetTransformInfo::getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                               int64_t Scale,
                                               unsigned AddrSpace) const {
   int Cost = TTIImpl->getScalingFactorCost(Ty, BaseGV, BaseOffset, HasBaseReg,
                                            Scale, AddrSpace);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
+bool TargetTransformInfo::LSRWithInstrQueries() const {
+  return TTIImpl->LSRWithInstrQueries();
+}
+
 bool TargetTransformInfo::isFoldableMemAccessOffset(Instruction *I,
                                                     int64_t Offset) const {
   return TTIImpl->isFoldableMemAccessOffset(I, Offset);
 }
 
 bool TargetTransformInfo::isTruncateFree(Type *Ty1, Type *Ty2) const {
   return TTIImpl->isTruncateFree(Ty1, Ty2);
 }

lib/CodeGen/TargetLoweringBase.cpp

 //===----------------------------------------------------------------------===//
 //  Loop Strength Reduction hooks
 //===----------------------------------------------------------------------===//
 
 /// isLegalAddressingMode - Return true if the addressing mode represented
 /// by AM is legal for this target, for a load/store of the specified type.
 bool TargetLoweringBase::isLegalAddressingMode(const DataLayout &DL,
                                                const AddrMode &AM, Type *Ty,
-                                               unsigned AS) const {
+                                               unsigned AS, Instruction *I) const {
   // The default implementation of this implements a conservative RISCy, r+r and
   // r+i addr mode.
 
   // Allows a sign-extended 16-bit immediate field.
   if (AM.BaseOffs <= -(1LL << 16) || AM.BaseOffs >= (1LL << 16)-1)
     return false;
 
   // No global is ever allowed as a base.

lib/Target/AArch64/AArch64ISelLowering.h

public:
 
   EVT getOptimalMemOpType(uint64_t Size, unsigned DstAlign, unsigned SrcAlign,
                           bool IsMemset, bool ZeroMemset, bool MemcpyStrSrc,
                           MachineFunction &MF) const override;
 
   /// Return true if the addressing mode represented by AM is legal for this
   /// target, for a load/store of the specified type.
   bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty,
-                             unsigned AS) const override;
+                             unsigned AS,
+                             Instruction *I = nullptr) const override;
 
   /// \brief Return the cost of the scaling factor used in the addressing
   /// mode represented by AM for this target, for a load/store
   /// of the specified type.
   /// If the AM is supported, the return value must be >= 0.
   /// If the AM is not supported, it returns a negative value.
   int getScalingFactorCost(const DataLayout &DL, const AddrMode &AM, Type *Ty,
                            unsigned AS) const override;

lib/Target/AArch64/AArch64ISelLowering.cpp

 bool AArch64TargetLowering::isLegalICmpImmediate(int64_t Immed) const {
   return isLegalAddImmediate(Immed);
 }
 
 /// isLegalAddressingMode - Return true if the addressing mode represented
 /// by AM is legal for this target, for a load/store of the specified type.
 bool AArch64TargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                                   const AddrMode &AM, Type *Ty,
-                                                  unsigned AS) const {
+                                                  unsigned AS, Instruction *I) const {
   // AArch64 has five basic addressing modes:
   //  reg
   //  reg + 9-bit signed offset
   //  reg + SIZE_IN_BYTES * 12-bit unsigned offset
   //  reg1 + reg2
   //  reg + SIZE_IN_BYTES * reg
 
   // No global is ever allowed as a base.

lib/Target/AMDGPU/SIISelLowering.h

public:
   bool getTgtMemIntrinsic(IntrinsicInfo &, const CallInst &,
                           unsigned IntrinsicID) const override;
 
   bool getAddrModeArguments(IntrinsicInst * /*I*/,
                             SmallVectorImpl<Value*> &/*Ops*/,
                             Type *&/*AccessTy*/) const override;
 
   bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty,
-                             unsigned AS) const override;
+                             unsigned AS,
+                             Instruction *I = nullptr) const override;
 
   bool canMergeStoresTo(unsigned AS, EVT MemVT) const override;
 
   bool allowsMisalignedMemoryAccesses(EVT VT, unsigned AS,
                                       unsigned Align,
                                       bool *IsFast) const override;
 
   EVT getOptimalMemOpType(uint64_t Size, unsigned DstAlign,

lib/Target/AMDGPU/SIISelLowering.cpp

case 2:
     return true;
   default: // Don't allow n * r
     return false;
   }
 }
 
 bool SITargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                              const AddrMode &AM, Type *Ty,
-                                             unsigned AS) const {
+                                             unsigned AS, Instruction *I) const {
   // No global is ever allowed as a base.
   if (AM.BaseGV)
     return false;
 
   if (AS == AMDGPUASI.GLOBAL_ADDRESS) {
     if (Subtarget->getGeneration() >= SISubtarget::VOLCANIC_ISLANDS) {
       // Assume the we will use FLAT for all global memory accesses
       // on VI.

lib/Target/ARM/ARMISelLowering.h

public:
     bool isVectorLoadExtDesirable(SDValue ExtVal) const override;
 
     bool allowTruncateForTailCall(Type *Ty1, Type *Ty2) const override;
 
 
     /// isLegalAddressingMode - Return true if the addressing mode represented
     /// by AM is legal for this target, for a load/store of the specified type.
     bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM,
-                               Type *Ty, unsigned AS) const override;
+                               Type *Ty, unsigned AS,
+                               Instruction *I = nullptr) const override;
 
     /// getScalingFactorCost - Return the cost of the scaling used in
     /// addressing mode represented by AM.
     /// If the AM is supported, the return value must be >= 0.
     /// If the AM is not supported, the return value must be negative.
     int getScalingFactorCost(const DataLayout &DL, const AddrMode &AM, Type *Ty,
                              unsigned AS) const override;
 

lib/Target/ARM/ARMISelLowering.cpp

     return isPowerOf2_32(Scale);
   }
 }
 
 /// isLegalAddressingMode - Return true if the addressing mode represented
 /// by AM is legal for this target, for a load/store of the specified type.
 bool ARMTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                               const AddrMode &AM, Type *Ty,
-                                              unsigned AS) const {
+                                              unsigned AS, Instruction *I) const {
   EVT VT = getValueType(DL, Ty, true);
   if (!isLegalAddressImmediate(AM.BaseOffs, VT, Subtarget))
     return false;
 
   // Can never fold addr of global into load/store.
   if (AM.BaseGV)
     return false;
 

lib/Target/AVR/AVRISelLowering.h

public:
   const char *getTargetNodeName(unsigned Opcode) const override;
 
   SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const override;
 
   void ReplaceNodeResults(SDNode *N, SmallVectorImpl<SDValue> &Results,
                           SelectionDAG &DAG) const override;
 
   bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty,
-                             unsigned AS) const override;
+                             unsigned AS,
+                             Instruction *I = nullptr) const override;
 
   bool getPreIndexedAddressParts(SDNode *N, SDValue &Base, SDValue &Offset,
                                  ISD::MemIndexedMode &AM,
                                  SelectionDAG &DAG) const override;
 
   bool getPostIndexedAddressParts(SDNode *N, SDNode *Op, SDValue &Base,
                                   SDValue &Offset, ISD::MemIndexedMode &AM,
                                   SelectionDAG &DAG) const override;

lib/Target/AVR/AVRISelLowering.cpp

void AVRTargetLowering::ReplaceNodeResults(SDNode *N,
   }
   }
 }
 
 /// Return true if the addressing mode represented
 /// by AM is legal for this target, for a load/store of the specified type.
 bool AVRTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                               const AddrMode &AM, Type *Ty,
-                                              unsigned AS) const {
+                                              unsigned AS, Instruction *I) const {
   int64_t Offs = AM.BaseOffs;
 
   // Allow absolute addresses.
   if (AM.BaseGV && !AM.HasBaseReg && AM.Scale == 0 && Offs == 0) {
     return true;
   }
 
   // Flash memory instructions only allow zero offsets.

lib/Target/Hexagon/HexagonISelLowering.h

public:
     SDValue LowerINTRINSIC_WO_CHAIN(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerINTRINSIC_VOID(SDValue Op, SelectionDAG &DAG) const;
     /// isLegalAddressingMode - Return true if the addressing mode represented
     /// by AM is legal for this target, for a load/store of the specified type.
     /// The type may be VoidTy, in which case only return true if the addressing
     /// mode is legal for a load/store of any legal type.
     /// TODO: Handle pre/postinc as well.
     bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM,
-                               Type *Ty, unsigned AS) const override;
+                               Type *Ty, unsigned AS,
+                               Instruction *I = nullptr) const override;
     /// Return true if folding a constant offset with the given GlobalAddress
     /// is legal.  It is frequently not legal in PIC relocation models.
     bool isOffsetFoldingLegal(const GlobalAddressSDNode *GA) const override;
 
     bool isFPImmLegal(const APFloat &Imm, EVT VT) const override;
 
     /// isLegalICmpImmediate - Return true if the specified immediate is legal
     /// icmp immediate, that is the target has icmp instructions which can

lib/Target/Hexagon/HexagonISelLowering.cpp

 bool HexagonTargetLowering::isFPImmLegal(const APFloat &Imm, EVT VT) const {
   return Subtarget.hasV5TOps();
 }
 
 /// isLegalAddressingMode - Return true if the addressing mode represented by
 /// AM is legal for this target, for a load/store of the specified type.
 bool HexagonTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                                   const AddrMode &AM, Type *Ty,
-                                                  unsigned AS) const {
+                                                  unsigned AS, Instruction *I) const {
   if (Ty->isSized()) {
     // When LSR detects uses of the same base address to access different
     // types (e.g. unions), it will assume a conservative type for these
     // uses:
     //   LSR Use: Kind=Address of void in addrspace(4294967295), ...
     // The type Ty passed here would then be "void". Skip the alignment
     // checks, but do not return false right away, since that confuses
     // LSR into crashing.

lib/Target/Mips/MipsISelLowering.h

getInlineAsmMemConstraint(StringRef ConstraintCode) const override {
       if (ConstraintCode == "R")
         return InlineAsm::Constraint_R;
       else if (ConstraintCode == "ZC")
         return InlineAsm::Constraint_ZC;
       return TargetLowering::getInlineAsmMemConstraint(ConstraintCode);
     }
 
     bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM,
-                               Type *Ty, unsigned AS) const override;
+                               Type *Ty, unsigned AS,
+                               Instruction *I = nullptr) const override;
 
     bool isOffsetFoldingLegal(const GlobalAddressSDNode *GA) const override;
 
     EVT getOptimalMemOpType(uint64_t Size, unsigned DstAlign,
                             unsigned SrcAlign,
                             bool IsMemset, bool ZeroMemset,
                             bool MemcpyStrSrc,
                             MachineFunction &MF) const override;

lib/Target/Mips/MipsISelLowering.cpp

if (Result.getNode()) {
     return;
   }
 
   TargetLowering::LowerAsmOperandForConstraint(Op, Constraint, Ops, DAG);
 }
 
 bool MipsTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                                const AddrMode &AM, Type *Ty,
-                                               unsigned AS) const {
+                                               unsigned AS, Instruction *I) const {
   // No global is ever allowed as a base.
   if (AM.BaseGV)
     return false;
 
   switch (AM.Scale) {
   case 0: // "r+i" or just "i", depending on HasBaseReg.
     break;
   case 1:

lib/Target/NVPTX/NVPTXISelLowering.h

bool getTgtMemIntrinsic(IntrinsicInfo &Info, const CallInst &I,
                           unsigned Intrinsic) const override;
 
   /// isLegalAddressingMode - Return true if the addressing mode represented
   /// by AM is legal for this target, for a load/store of the specified type
   /// Used to guide target specific optimizations, like loop strength
   /// reduction (LoopStrengthReduce.cpp) and memory optimization for
   /// address mode (CodeGenPrepare.cpp)
   bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty,
-                             unsigned AS) const override;
+                             unsigned AS,
+                             Instruction *I = nullptr) const override;
 
   bool isTruncateFree(Type *SrcTy, Type *DstTy) const override {
     // Truncating 64-bit to 32-bit is free in SASS.
     if (!SrcTy->isIntegerTy() || !DstTy->isIntegerTy())
       return false;
     return SrcTy->getPrimitiveSizeInBits() == 64 &&
            DstTy->getPrimitiveSizeInBits() == 32;
   }

lib/Target/NVPTX/NVPTXISelLowering.cpp

 
 /// isLegalAddressingMode - Return true if the addressing mode represented
 /// by AM is legal for this target, for a load/store of the specified type.
 /// Used to guide target specific optimizations, like loop strength reduction
 /// (LoopStrengthReduce.cpp) and memory optimization for address mode
 /// (CodeGenPrepare.cpp)
 bool NVPTXTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                                 const AddrMode &AM, Type *Ty,
-                                                unsigned AS) const {
+                                                unsigned AS, Instruction *I) const {
   // AddrMode - This represents an addressing mode of:
   //    BaseGV + BaseOffs + BaseReg + Scale*ScaleReg
   //
   // The legal address modes are
   // - [avar]
   // - [areg]
   // - [areg+immoff]
   // - [immAddr]

lib/Target/PowerPC/PPCISelLowering.h

getInlineAsmMemConstraint(StringRef ConstraintCode) const override {
       else if (ConstraintCode == "Zy")
         return InlineAsm::Constraint_Zy;
       return TargetLowering::getInlineAsmMemConstraint(ConstraintCode);
     }
 
     /// isLegalAddressingMode - Return true if the addressing mode represented
     /// by AM is legal for this target, for a load/store of the specified type.
     bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM,
-                               Type *Ty, unsigned AS) const override;
+                               Type *Ty, unsigned AS,
+                               Instruction *I = nullptr) const override;
 
     /// isLegalICmpImmediate - Return true if the specified immediate is legal
     /// icmp immediate, that is the target has icmp instructions which can
     /// compare a register against the immediate without having to materialize
     /// the immediate into a register.
     bool isLegalICmpImmediate(int64_t Imm) const override;
 
     /// isLegalAddImmediate - Return true if the specified immediate is legal

lib/Target/PowerPC/PPCISelLowering.cpp

   // Handle standard constraint letters.
   TargetLowering::LowerAsmOperandForConstraint(Op, Constraint, Ops, DAG);
 }
 
 // isLegalAddressingMode - Return true if the addressing mode represented
 // by AM is legal for this target, for a load/store of the specified type.
 bool PPCTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                               const AddrMode &AM, Type *Ty,
-                                              unsigned AS) const {
+                                              unsigned AS, Instruction *I) const {
   // PPC does not allow r+i addressing modes for vectors!
   if (Ty->isVectorTy() && AM.BaseOffs != 0)
     return false;
 
   // PPC allows a sign-extended 16-bit immediate field.
   if (AM.BaseOffs <= -(1LL << 16) || AM.BaseOffs >= (1LL << 16)-1)
     return false;
 

lib/Target/SystemZ/SystemZISelLowering.h

public:
   }
   EVT getSetCCResultType(const DataLayout &DL, LLVMContext &,
                          EVT) const override;
   bool isFMAFasterThanFMulAndFAdd(EVT VT) const override;
   bool isFPImmLegal(const APFloat &Imm, EVT VT) const override;
   bool isLegalICmpImmediate(int64_t Imm) const override;
   bool isLegalAddImmediate(int64_t Imm) const override;
   bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty,
-                             unsigned AS) const override;
+                             unsigned AS,
+                             Instruction *I = nullptr) const override;
   bool isFoldableMemAccessOffset(Instruction *I, int64_t Offset) const override;
   bool allowsMisalignedMemoryAccesses(EVT VT, unsigned AS,
                                       unsigned Align,
                                       bool *Fast) const override;
   bool isTruncateFree(Type *, Type *) const override;
   bool isTruncateFree(EVT, EVT) const override;
   const char *getTargetNodeName(unsigned Opcode) const override;
   std::pair<unsigned, const TargetRegisterClass *>

lib/Target/SystemZ/SystemZISelLowering.cpp

bool SystemZTargetLowering::allowsMisalignedMemoryAccesses(EVT VT,
   // Unaligned accesses should never be slower than the expanded version.
   // We check specifically for aligned accesses in the few cases where
   // they are required.
   if (Fast)
     *Fast = true;
   return true;
 }
 
+// When checking for immediate offsets for Load->Store, it is beneficial
+// generally to keep them small also for the non i8 case, since it is not
+// that uncommon that isel folds adjacent load->stores into vector
+// operations, which also needs small offsets.
+static bool hasLessAddressing(Instruction *I, bool Offsets = false) {
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+    switch (II->getIntrinsicID()) {
+    default: break;
+    case Intrinsic::memset:
+    case Intrinsic::memmove:
+    case Intrinsic::memcpy:
+      return true;
+    }
+  }
+
+  if (isa<LoadInst>(I) && I->hasOneUse()) {
+    auto *SingleUser = dyn_cast<Instruction>(*I->user_begin());
+    if (SingleUser->getParent() == I->getParent()) {
+      if (isa<ICmpInst>(SingleUser)) {
+        if (auto *C = dyn_cast<ConstantInt>(SingleUser->getOperand(1)))
+          if (isInt<16>(C->getSExtValue()) || isUInt<16>(C->getZExtValue()))
+            // Comparison of memory with 16 bit signed / unsigned immediate
+            return true;
+      } else if (Offsets && isa<StoreInst>(SingleUser))
+        // Load->Store: MVC
+        return true;
+    }
+  } else if (auto *StoreI = dyn_cast<StoreInst>(I)) {
+    if (auto *LoadI = dyn_cast<LoadInst>(StoreI->getValueOperand()))
+      if (Offsets && (LoadI->hasOneUse() && LoadI->getParent() == I->getParent()))
+        // Load->Store: MVC
+        return true;
+  }
+
+  return false;
+}
+
+static bool needsD12(Instruction *I) {
+  return hasLessAddressing(I, true);
+}
+
+static bool hasNoIndexReg(Instruction *I) {
+  return hasLessAddressing(I, false);
+}
+
 bool SystemZTargetLowering::isLegalAddressingMode(const DataLayout &DL,
-                                                  const AddrMode &AM, Type *Ty,
-                                                  unsigned AS) const {
+            const AddrMode &AM, Type *Ty, unsigned AS, Instruction *I) const {
+
+  if (AM.Scale != 0 && I != nullptr && hasNoIndexReg(I))
+    return false;
+
   // Punt on globals for now, although they can be used in limited
   // RELATIVE LONG cases.
   if (AM.BaseGV)
     return false;
 
   // Require a 20-bit signed offset.
   if (!isInt<20>(AM.BaseOffs))
     return false;
 
   // Indexing is OK but no scale factor can be applied.
   return AM.Scale == 0 || AM.Scale == 1;
 }
 
 bool SystemZTargetLowering::isFoldableMemAccessOffset(Instruction *I,
                                                       int64_t Offset) const {
+  if (needsD12(I))
+      return (isUInt<12>(Offset));
+
+  if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
+    return true;
+
   // This only applies to z13.
   if (!Subtarget.hasVector())
     return true;
 
   // * Use LDE instead of LE/LEY to avoid partial register
   //   dependencies (LDE only supports small offsets).
   // * Utilize the vector registers to hold floating point
   //   values (vector load / store instructions only support small
   //   offsets).
 
-  assert (isa<LoadInst>(I) || isa<StoreInst>(I));
   Type *MemAccessTy = (isa<LoadInst>(I) ? I->getType() :
                        I->getOperand(0)->getType());
   bool IsFPAccess = MemAccessTy->isFloatingPointTy();
   bool IsVectorAccess = MemAccessTy->isVectorTy();
 
   // A store of an extracted vector element will be combined into a VSTE type
   // instruction.
   if (!IsVectorAccess && isa<StoreInst>(I)) {
     Value *DataOp = I->getOperand(0);
     if (isa<ExtractElementInst>(DataOp))
       IsVectorAccess = true;
   }
 
   // A load which gets inserted into a vector element will be combined into a
   // VLE type instruction.
   if (!IsVectorAccess && isa<LoadInst>(I) && I->hasOneUse()) {
     User *LoadUser = *I->user_begin();
     if (isa<InsertElementInst>(LoadUser))
       IsVectorAccess = true;
   }
 
   if (!isUInt<12>(Offset) && (IsFPAccess || IsVectorAccess))
     return false;
 
   return true;
 }
 
 bool SystemZTargetLowering::isTruncateFree(Type *FromType, Type *ToType) const {
   if (!FromType->isIntegerTy() || !ToType->isIntegerTy())
     return false;
   unsigned FromBits = FromType->getPrimitiveSizeInBits();
   unsigned ToBits = ToType->getPrimitiveSizeInBits();
   return FromBits > ToBits;

lib/Target/SystemZ/SystemZTargetTransformInfo.h

public:
   int getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm, Type *Ty);
   int getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                     Type *Ty);
 
   TTI::PopcntSupportKind getPopcntSupport(unsigned TyWidth);
 
   void getUnrollingPreferences(Loop *L, TTI::UnrollingPreferences &UP);
 
+  bool isLSRCostLess(TargetTransformInfo::LSRCost &C1,
+                     TargetTransformInfo::LSRCost &C2);
   /// @}
 
   /// \name Vector TTI Implementations
   /// @{
 
   unsigned getNumberOfRegisters(bool Vector);
   unsigned getRegisterBitWidth(bool Vector) const;
 
   bool prefersVectorizedAddressing() { return false; }
+  bool LSRWithInstrQueries() { return true; }
   bool supportsEfficientVectorElementLoadStore() { return true; }
   bool enableInterleavedAccessVectorization() { return true; }
 
   int getArithmeticInstrCost(
       unsigned Opcode, Type *Ty,
       TTI::OperandValueKind Opd1Info = TTI::OK_AnyValue,
       TTI::OperandValueKind Opd2Info = TTI::OK_AnyValue,
       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,

lib/Target/SystemZ/SystemZTargetTransformInfo.cpp

void SystemZTTIImpl::getUnrollingPreferences(Loop *L,
   UP.DefaultUnrollRuntimeCount = 4;
 
   // Allow expensive instructions in the pre-header of the loop.
   UP.AllowExpensiveTripCount = true;
 
   UP.Force = true;
 }
 
+
+bool SystemZTTIImpl::isLSRCostLess(TargetTransformInfo::LSRCost &C1,
+                                   TargetTransformInfo::LSRCost &C2) {
+  // SystemZ specific: check instruction count (first).
+  return std::tie(C1.Insns, C1.NumRegs, C1.AddRecCost,
+                  C1.NumIVMuls, C1.NumBaseAdds,
+                  C1.ScaleCost, C1.ImmCost, C1.SetupCost) <
+    std::tie(C2.Insns, C2.NumRegs, C2.AddRecCost,
+             C2.NumIVMuls, C2.NumBaseAdds,
+             C2.ScaleCost, C2.ImmCost, C2.SetupCost);
+}
+
 unsigned SystemZTTIImpl::getNumberOfRegisters(bool Vector) {
   if (!Vector)
     // Discount the stack pointer.  Also leave out %r0, since it can't
     // be used in an address.
     return 14;
   if (ST->hasVector())
     return 32;
   return 0;

lib/Target/WebAssembly/WebAssemblyISelLowering.h

private:
   MVT getScalarShiftAmountTy(const DataLayout &DL, EVT) const override;
   const char *getTargetNodeName(unsigned Opcode) const override;
   std::pair<unsigned, const TargetRegisterClass *> getRegForInlineAsmConstraint(
       const TargetRegisterInfo *TRI, StringRef Constraint,
       MVT VT) const override;
   bool isCheapToSpeculateCttz() const override;
   bool isCheapToSpeculateCtlz() const override;
   bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty,
-                             unsigned AS) const override;
+                             unsigned AS,
+                             Instruction *I = nullptr) const override;
   bool allowsMisalignedMemoryAccesses(EVT, unsigned AddrSpace, unsigned Align,
                                       bool *Fast) const override;
   bool isIntDivCheap(EVT VT, AttributeList Attr) const override;
 
   SDValue LowerCall(CallLoweringInfo &CLI,
                     SmallVectorImpl<SDValue> &InVals) const override;
   bool CanLowerReturn(CallingConv::ID CallConv, MachineFunction &MF,
                       bool isVarArg,

lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

 bool WebAssemblyTargetLowering::isCheapToSpeculateCtlz() const {
   // Assume clz is a relatively cheap operation.
   return true;
 }
 
 bool WebAssemblyTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                                       const AddrMode &AM,
                                                       Type *Ty,
-                                                      unsigned AS) const {
+                                                      unsigned AS,
+                                                      Instruction *I) const {
   // WebAssembly offsets are added as unsigned without wrapping. The
   // isLegalAddressingMode gives us no way to determine if wrapping could be
   // happening, so we approximate this by accepting only non-negative offsets.
   if (AM.BaseOffs < 0) return false;
 
   // WebAssembly has no scale register operands.
   if (AM.Scale != 0) return false;
 

lib/Target/X86/X86ISelLowering.h

public:
     /// error, this returns a register number of 0.
     std::pair<unsigned, const TargetRegisterClass *>
     getRegForInlineAsmConstraint(const TargetRegisterInfo *TRI,
                                  StringRef Constraint, MVT VT) const override;
 
     /// Return true if the addressing mode represented
     /// by AM is legal for this target, for a load/store of the specified type.
     bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM,
-                               Type *Ty, unsigned AS) const override;
+                               Type *Ty, unsigned AS,
+                               Instruction *I = nullptr) const override;
 
     /// Return true if the specified immediate is legal
     /// icmp immediate, that is the target has icmp instructions which can
     /// compare a register against the immediate without having to materialize
     /// the immediate into a register.
     bool isLegalICmpImmediate(int64_t Imm) const override;
 
     /// Return true if the specified immediate is legal

lib/Target/X86/X86ISelLowering.cpp

   }
   return nullptr;
 }
 
 /// Return true if the addressing mode represented by AM is legal for this
 /// target, for a load/store of the specified type.
 bool X86TargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                               const AddrMode &AM, Type *Ty,
-                                              unsigned AS) const {
+                                              unsigned AS,
+                                              Instruction *I) const {
   // X86 supports extremely general addressing modes.
   CodeModel::Model M = getTargetMachine().getCodeModel();
 
   // X86 allows a sign-extended 32-bit immediate field as a displacement.
   if (!X86::isOffsetSuitableForCodeModel(AM.BaseOffs, M, AM.BaseGV != nullptr))
     return false;
 
   if (AM.BaseGV) {

lib/Target/XCore/XCoreISelLowering.h

public:
     //  DAG node.
     const char *getTargetNodeName(unsigned Opcode) const override;
 
     MachineBasicBlock *
     EmitInstrWithCustomInserter(MachineInstr &MI,
                                 MachineBasicBlock *MBB) const override;
 
     bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM,
-                               Type *Ty, unsigned AS) const override;
+                               Type *Ty, unsigned AS,
+                               Instruction *I = nullptr) const override;
 
     /// If a physical register, this returns the register that receives the
     /// exception address on entry to an EH pad.
     unsigned
     getExceptionPointerRegister(const Constant *PersonalityFn) const override {
       return XCore::R0;
     }
 

lib/Target/XCore/XCoreISelLowering.cpp

 {
   return (val%4 == 0 && isImmUs(val/4));
 }
 
 /// isLegalAddressingMode - Return true if the addressing mode represented
 /// by AM is legal for this target, for a load/store of the specified type.
 bool XCoreTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                                 const AddrMode &AM, Type *Ty,
-                                                unsigned AS) const {
+                                                unsigned AS,
+                                                Instruction *I) const {
   if (Ty->getTypeID() == Type::VoidTyID)
     return AM.Scale == 0 && isImmUs(AM.BaseOffs) && isImmUs4(AM.BaseOffs);
 
   unsigned Size = DL.getTypeAllocSize(Ty);
   if (AM.BaseGV) {
     return Size >= 4 && !AM.HasBaseReg && AM.Scale == 0 &&
                  AM.BaseOffs%4 == 0;
   }

lib/Transforms/Scalar/LoopStrengthReduce.cpp

static bool isAddressUse(Instruction *Inst, Value *OperandVal) {
   if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
     if (SI->getPointerOperand() == OperandVal)
       isAddress = true;
   } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
     // Addressing modes can also be folded into prefetches and a variety
     // of intrinsics.
     switch (II->getIntrinsicID()) {
       default: break;
+      case Intrinsic::memset:
       case Intrinsic::prefetch:
         if (II->getArgOperand(0) == OperandVal)
           isAddress = true;
         break;
+      case Intrinsic::memmove:
+      case Intrinsic::memcpy:
+        if (II->getArgOperand(0) == OperandVal ||
+            II->getArgOperand(1) == OperandVal)
+          isAddress = true;
+        break;
     }
   } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(Inst)) {
     if (RMW->getPointerOperand() == OperandVal)
       isAddress = true;
   } else if (AtomicCmpXchgInst *CmpX = dyn_cast<AtomicCmpXchgInst>(Inst)) {
     if (CmpX->getPointerOperand() == OperandVal)
       isAddress = true;
   }
void Cost::RateFormula(const TargetTransformInfo &TTI,
 
   // Tally up the non-zero immediates.
   for (const LSRFixup &Fixup : LU.Fixups) {
     int64_t O = Fixup.Offset;
     int64_t Offset = (uint64_t)O + F.BaseOffset;
     if (F.BaseGV)
       C.ImmCost += 64; // Handle symbolic values conservatively.
                      // TODO: This should probably be the pointer size.
-    else if (Offset != 0)
-      C.ImmCost += APInt(64, Offset, true).getMinSignedBits();
 
-    // Check with target if this offset with this instruction is
-    // specifically not supported.
-    if ((isa<LoadInst>(Fixup.UserInst) || isa<StoreInst>(Fixup.UserInst)) &&
-        !TTI.isFoldableMemAccessOffset(Fixup.UserInst, Offset))
+    if (Offset == 0)
+      continue;
+
+    if (LU.Kind == LSRUse::Address && TTI.LSRWithInstrQueries()) {
+      if (!TTI.isFoldableMemAccessOffset(Fixup.UserInst, Offset))
         C.NumBaseAdds++;
+    } else
+      C.ImmCost += APInt(64, Offset, true).getMinSignedBits();
   }
 
   // If we don't count instruction cost exit here.
   if (!InsnsCost) {
     assert(isValid() && "invalid cost");
     return;
   }
 
static bool isLegalUse(const TargetTransformInfo &TTI, int64_t MinOffset,
                        int64_t MaxOffset, LSRUse::KindType Kind,
                        MemAccessTy AccessTy, const Formula &F) {
   return isLegalUse(TTI, MinOffset, MaxOffset, Kind, AccessTy, F.BaseGV,
                     F.BaseOffset, F.HasBaseReg, F.Scale);
 }
 
 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
                                  const LSRUse &LU, const Formula &F) {
+  // Target may want to look at the user instructions.
+  if (LU.Kind == LSRUse::Address && TTI.LSRWithInstrQueries()) {
+    for (const LSRFixup &Fixup : LU.Fixups)
+      if (!TTI.isLegalAddressingMode(LU.AccessTy.MemTy, F.BaseGV, F.BaseOffset,
+                                     F.HasBaseReg, F.Scale, LU.AccessTy.AddrSpace,
+                                     Fixup.UserInst))
+        return false;
+    return true;
+  }
+
   return isAMCompletelyFolded(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind,
                               LU.AccessTy, F.BaseGV, F.BaseOffset, F.HasBaseReg,
                               F.Scale);
 }
 
 static unsigned getScalingFactorCost(const TargetTransformInfo &TTI,
                                      const LSRUse &LU, const Formula &F,
                                      const Loop &L) {

test/CodeGen/SystemZ/dag-combine-01.ll

for.body.3.lr.ph.i:                               ; preds = %for.body.3.lr.ph.i.preheader, %for.inc.40.i
   %indvars.iv57.i = phi i64 [ 1, %for.body.3.lr.ph.i.preheader ], [ %indvars.iv.next58.i, %for.inc.40.i ]
   %1 = shl nsw i64 %indvars.iv57.i, 1
   %2 = shl nsw i64 %indvars.iv57.i, 6
   br label %for.body.3.i
 
 for.body.3.i:                                     ; preds = %for.body.3.i, %for.body.3.lr.ph.i
 ; CHECK-LABEL: .LBB0_5:
 ; CHECK-NOT:    stfh    %r{{.*}}, 0(%r{{.*}})
-; CHECK:        lg      %r{{.*}}, -4(%r{{.*}})
+; CHECK:        lg      %r{{.*}}, 8(%r{{.*}})
 ; Overlapping load should go before the store
   %indvars.iv.i = phi i64 [ 0, %for.body.3.lr.ph.i ], [ %indvars.iv.next.i, %for.body.3.i ]
   %3 = shl nsw i64 %indvars.iv.i, 6
   %4 = add nuw nsw i64 %3, %1
   %arrayidx.i = getelementptr inbounds [2048 x float], [2048 x float]* @A, i64 0, i64 %4
   %5 = bitcast float* %arrayidx.i to i32*
   %6 = load i32, i32* %5, align 4
   %arrayidx9.i = getelementptr inbounds float, float* getelementptr inbounds ([2048 x float], [2048 x float]* @A, i64 0, i64 1), i64 %4

test/CodeGen/SystemZ/loop-01.ll

 ; Test loop tuning.
 ;
 ; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z10 | FileCheck %s
 ; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z13 \
 ; RUN:  | FileCheck %s -check-prefix=CHECK -check-prefix=CHECK-Z13
 
 ; Test that strength reduction is applied to addresses with a scale factor,
 ; but that indexed addressing can still be used.
 define void @f1(i32 *%dest, i32 %a) {
 ; CHECK-LABEL: f1:
 ; CHECK-NOT: sllg
-; CHECK: st %r3, 0({{%r[1-5],%r[1-5]}})
+; CHECK: st %r3, 400({{%r[1-5],%r[1-5]}})
 ; CHECK: br %r14
 entry:
   br label %loop
 
 loop:
   %index = phi i64 [ 0, %entry ], [ %next, %loop ]
   %ptr = getelementptr i32, i32 *%dest, i64 %index
   store i32 %a, i32 *%ptr
for.body:                           ; preds = %for.body.preheader, %for.body
   %add7 = add <4 x i32> %add, %tmp2
   %a10 = getelementptr inbounds %s.vec, %s.vec* %a, i64 %indvars.iv, i32 0
   store <4 x i32> %add7, <4 x i32>* %a10, align 4
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, %S
   br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body
 }
+
+; Test that a memcpy loop does not get a lot of lays before each mvc (D12 and no index-reg).
+%0 = type { %1, %2* }
+%1 = type { %2*, %2* }
+%2 = type <{ %3, i32, [4 x i8] }>
+%3 = type { i16*, i16*, i16* }
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1) #0
+
+define void @f8() {
+; CHECK-Z13-LABEL: f8:
+; CHECK-Z13: mvc
+; CHECK-Z13-NEXT: mvc
+; CHECK-Z13-NEXT: mvc
+; CHECK-Z13-NEXT: mvc
+
+  %1 = load %0*, %0** undef, align 8
+  br i1 undef, label %3, label %2
+
+; <label>:2:                                      ; preds = %0
+  br label %3
+
+; <label>:3:                                      ; preds = %2, %0
+  %4 = phi %0* [ %1, %0 ], [ undef, %2 ]
+  %5 = phi %0* [ undef, %0 ], [ undef, %2 ]
+  br label %6
+
+; <label>:6:                                      ; preds = %6, %3
+  %7 = phi %0* [ %22, %6 ], [ %4, %3 ]
+  %8 = phi %0* [ %21, %6 ], [ %5, %3 ]
+  %9 = getelementptr inbounds %0, %0* %8, i64 -1
+  %10 = getelementptr inbounds %0, %0* %7, i64 -1
+  %11 = bitcast %0* %10 to i8*
+  %12 = bitcast %0* %9 to i8*
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %11, i8* %12, i64 24, i32 8, i1 false)
+  %13 = getelementptr inbounds %0, %0* %8, i64 -2
+  %14 = getelementptr inbounds %0, %0* %7, i64 -2
+  %15 = bitcast %0* %14 to i8*
+  %16 = bitcast %0* %13 to i8*
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %15, i8* %16, i64 24, i32 8, i1 false)
+  %17 = getelementptr inbounds %0, %0* %8, i64 -3
+  %18 = getelementptr inbounds %0, %0* %7, i64 -3
+  %19 = bitcast %0* %18 to i8*
+  %20 = bitcast %0* %17 to i8*
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %19, i8* %20, i64 24, i32 8, i1 false)
+  %21 = getelementptr inbounds %0, %0* %8, i64 -4
+  %22 = getelementptr inbounds %0, %0* %7, i64 -4
+  %23 = bitcast %0* %22 to i8*
+  %24 = bitcast %0* %21 to i8*
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %23, i8* %24, i64 24, i32 8, i1 false)
+  br label %6
+}
+
+; Test that a chsi does not need an aghik inside the loop (no index reg)
+define void @f9() {
+; CHECK-Z13-LABEL: f9:
+; CHECK-Z13: # =>This Inner Loop Header: Depth=1
+; CHECK-Z13-NOT: aghik
+; CHECK-Z13: chsi
+
+entry:
+  br label %for.body.i63
+
+for.body.i63:                                     ; preds = %for.inc.i, %entry
+  %indvars.iv155.i = phi i64 [ 0, %entry ], [ %indvars.iv.next156.i.3, %for.inc.i ]
+  %arrayidx.i62 = getelementptr inbounds i32, i32* undef, i64 %indvars.iv155.i
+  %0 = load i32, i32* %arrayidx.i62, align 4
+  %cmp9.i = icmp eq i32 %0, 0
+  br i1 %cmp9.i, label %for.inc.i, label %if.then10.i
+
+if.then10.i:                                      ; preds = %for.body.i63
+  unreachable
+
+for.inc.i:                                        ; preds = %for.body.i63
+  %indvars.iv.next156.i = or i64 %indvars.iv155.i, 1
+  %arrayidx.i62.1 = getelementptr inbounds i32, i32* undef, i64 %indvars.iv.next156.i
+  %1 = load i32, i32* %arrayidx.i62.1, align 4
+  %indvars.iv.next156.i.3 = add nsw i64 %indvars.iv155.i, 4
+  br label %for.body.i63
+}