Improve LoopStrengthReduce RateFormula, by calling a new target hook increasedLSRFormulaCost()

[jonpa]

Summary

While experimenting with the LoopUnroller pass for SystemZ, it was obvious that some loops regressed, due to the fact that LSR introduced negative offsets for load / store operations. These require an extra load-address instruction for float and vector types on SystemZ..

To be able to avoid this, I tried using isLegalAddressingMode() by returning false for float / double. This however caused other regressions.
Therefore I had to add a new method to TargetTransformInfo which adds an extra cost for the where appropriate. It seems to make sense generally to let targets adjust LSR formula rating.

During rating of formulas, the new TTI method needs to look at the actual user instructions. This was a bit awkward to get in place, and it may very well be that the code owner of this file could do a better job of it, or do some refactoring. I resorted to passing the Fixups to RateFormula, while letting the LSRUse access the right LSRFixup by means of an index. I had to rearrange code a bit to be able to use the LSRFixup class as an argument to RateFormula.

This seems to be the only viable way of using partial / runtime loop unrolling on SystemZ.

[jonpa]

ping

(Once again, this patch isn't really that big except I had to move up a class definition, so it just looks that way.)

The question that this patch answers is "Does this memory access (load/store, type) with the new total offset require an extra reg add?".

Perhaps this should be part of isAMCompletelyFolded()?

[hfinkel]

Could this problem be solved in the backend by implementing needsFrameBaseReg, materializeFrameBaseRegister, resolveFrameIndex and isFrameOffsetLegal in SystemZRegisterInfo.{h,cpp}?

I have no fundamental problem with the target being able to adjust the LSR formula costs, but the specific problem described seems to be what the virtual base register functionality should address.

lib/Target/SystemZ/SystemZISelLowering.cpp

31

rm extra blank line.

[jonpa]

I don't think the RegisterInfo methods you mention will do the trick, as they all handle just frame index operands, meaning variables on the stack. Wouldn't that still leave e.g. global variables and argument addresses unhandled? Besides, since this relates to loops, even a simple extra register load could perhaps be worth avoiding.

The motivation for an LSR target cost adjustment is that it seems to be a good way to improve performance while avoiding regressions. As I said earlier, I tried using isLegalAddressingMode(), but that also caused regressions. I think this difference is because SystemZ actually has support for loading with big offset of float values. However, as those loads get folded into their uses an extra load-address instruction is emitted if the offset is negative. The instructions with a folded memory-operand only support small offsets.

I am not really sure about the way LoopStrengthReduce.cpp is organized. It seems intuitive to me that the LSRUse class should know about the actual user instructions (lsr-fixups). This was not the case, so I added just the indexes of the LSRFixups to LSRUse, since the fixups are stored in LSRInstance. This has the drawback of having to pass the Fixups vector to RateFormula as well, so that the LSRUse can index into it. Perhaps the LSRUse class should own the fixups instead?

[hfinkel]

In D19152#413455, @jonpa wrote:

I don't think the RegisterInfo methods you mention will do the trick, as they all handle just frame index operands, meaning variables on the stack. Wouldn't that still leave e.g. global variables and argument addresses unhandled? Besides, since this relates to loops, even a simple extra register load could perhaps be worth avoiding.

This makes sense.

The motivation for an LSR target cost adjustment is that it seems to be a good way to improve performance while avoiding regressions. As I said earlier, I tried using isLegalAddressingMode(), but that also caused regressions. I think this difference is because SystemZ actually has support for loading with big offset of float values. However, as those loads get folded into their uses an extra load-address instruction is emitted if the offset is negative. The instructions with a folded memory-operand only support small offsets.

I am not really sure about the way LoopStrengthReduce.cpp is organized. It seems intuitive to me that the LSRUse class should know about the actual user instructions (lsr-fixups). This was not the case, so I added just the indexes of the LSRFixups to LSRUse, since the fixups are stored in LSRInstance. This has the drawback of having to pass the Fixups vector to RateFormula as well, so that the LSRUse can index into it. Perhaps the LSRUse class should own the fixups instead?

Andy, Quentin, Adam, Sanjoy, et al., opinions?

[atrick]

Adding TTI hooks in LSR is fine with me. increasedLSRFormulaCost seems a little specific though for a TTI hook.

Iterating over Fixups.Offset does seem redundant with LSRUse.Offsets. My general concern is really the growing complexity of LSR utilities, with multiple ways of handling the same instruction set problems. I feels to me like this is something that should be handled by isAlwaysFoldable.

Can someone else take a look at this? Adam, MichaelZ, Quentin?

[qcolombet]

Hi Jonas,

I share Andy’s points:

• This seems redundant with LU.Offsets.
• That may be accounted within isAlwaysFoldable.

Could you add a test case to see how things are playing together?

Cheers,
-Quentin

[jonpa]

The SystemZTargetLowering::increasedLSRFormulaCost() has been extended to consider vector store instructions also.

[jonpa]

Hi Andy and Quentin,

thanks for review so far!

My feeling is that looking at LU.Offsets is not enough, since not all offsets of all user instructions are guaranteed / supposed to be present in the Offsets vector.

Using isAlwaysFoldable() also seems difficult, since there is no info about if the user instruction is a store or a load.

These two parameters are what is needed to make a proper cost function, at least for SystemZ, since it makes a difference if the user instruction is a load or a store (see the implementation in this patch).

One alternative to iterating over the LSRFixups (use instructions) may be to make sure *all* LU.Offsets are present in the vector, and also have keep track of load / store type for each offset somehow.

Another thought is to extend MemAccessTy (or KindType) with load / store attribute, although, that seems problematic since then stores and loads would then not belong to the same LSRUse even if they are otherwise compatible.

It may also be possible to compromise and ignore the load / store differences, but that is of course not as good.

What are your thoughts on this?

/Jonas

PS will send test case in separate mail

[jonpa]

Patch updated so that

• LSRUse will own its fixups instead of indexes into the LSRFixups vector.
• Renamed the new method to isFoldableMemAccessOffset(), since it really isn't an LSR specific function.

I think it's generally useful to let the LSRUse own its fixups, and as Andy pointed out, the Offsets vector is not necessary if already iterating over the fixups, so that vector has been removed. (And again, class definitions have been moved around, so it looks like more changes than there really are).

LSR is with this patch *NOT* making entirely identical decisions. In RateFormula all fixup offets are now considered, whereas before Offsets were a bit sloppily kept unique, without any guarantee of them being so. From what I could quickly see, there seems to be less or smaller offsets used with the patch applied, which means it seems to be some welcome changes here and there. Perhaps someone could look over the logic under "Tally up the non-zero immediates." in RateFormula(), which is where this effect comes into play?

The new TargetTransformInfo hook could be considered a complement to isLegalAddressingMode(), which is more of a high level, while this new method is a more precise cost function with the Instruction included as argument. Perhaps they could be merged somehow, but I am not sure that is the right thing to do.

There is a myriad of isAlwaysFoldable() and isAMCompletelyFolded() functions used in LSR. There is also the Formula::UnfoldedOffset and the MaxOffset and MinOffset of the LSRUse which all play a role in the handling of immediate offsets. I am not sure about all the reasoning behind all this, so I have now only done the simple thing by adding this new cost function in RateFormula(). It may be that it could / should be used at earlier stages also, for efficiency's sake.

Even if this is not a complete reworking of LSR, I think this patch is a refactoring in the right direction, along with a needed improvement for SystemZ.

[jonpa]

Just to clarify: LSR results are changed by both 1) Considering all LSRFixups instead of the old Offsets vector. This gives a little different ImmCost sums. 2) The new target hook, which may add 1 to NumBaseAdds.

[qcolombet]

Thanks for the clarifications and updates.

Will have a closer look.

[qcolombet]

Hi Jonas,

The updated patch makes sense to me.
The patch is missing a test case though.

@Andy, do you have any additional comment?

Cheers,
-Quentin

include/llvm/Analysis/TargetTransformInfo.h

340

We should mention that the addressing mode is of the form reg + Offset.

[jonpa]

Comment fixed as suggested.
New tests for the SystemZ backend.

[qcolombet]

test/CodeGen/SystemZ/loop-01.ll

5 ↗

(On Diff #59859)

How different is the codegen for the z13 cpu?
The reason why I am asking is because right now, the test cases are partitioned between one target and the other with no overlap whereas if we have several RUN command in the file, I would have expected at least some overlap.

I.e., I would expect a common prefix between both CPUs that is used for most of the tests.

152 ↗

(On Diff #59859)

Use "opt -instnamer" to get %[0-9]+ variables.

[jonpa]

test/CodeGen/SystemZ/loop-01.ll

5 ↗

(On Diff #59859)

The one test for z13 is for vector instructions, which only z13 supports.

The other tests I added should be common for all subtargets, so I just reused the already present RUN command. Perhaps it should use the generic subtarget instead of z10 (which I think would be equivalent)?

[jonpa]

test/CodeGen/SystemZ/loop-01.ll

152 ↗

(On Diff #59859)

It seems to replace %[0-9]+ variable names with %tmp[1-9]* names. Is that what you want?

[uweigand]

The other tests I added should be common for all subtargets, so I just reused the already present RUN command. Perhaps it should use the generic subtarget instead of z10 (which I think would be equivalent)?

In the past, LLVM would default to detecting the host CPU when compiling natively, which would cause random test failures depending on the particular host that was running the test suite. To fix this, most tests hard-coded a z10 CPU.

These days, this is no longer necessary since LLVM no longer defaults to automatically detecting the CPU, but always defaults to z10 anyway.

[qcolombet]

test/CodeGen/SystemZ/loop-01.ll

5 ↗

(On Diff #59859)

In that case, for the RUN line with z13 also add —check-prefix=CHECK.

152 ↗

(On Diff #59859)

Yes, that what I want.
[0-9]+ variables cannot be reordered or removed, tmp[0-9]+ can :).

[jonpa]

Updated per review:
-check-prefix=CHECK added to -z13 RUN line so that all tests run for -z13 as well.
New tests filtered through opt -instnamer, to eliminate numeral based instruction names.

[qcolombet]

LGTM.

[jonpa]

I know this patch was approved already, but I have made some minor changes, which might as well get review since this hasn't been commited yet.

• Added a check so that the new function is only called for loads and stores, after realizing it also gets called on PHIs etc.

+ if ((isa<LoadInst>(Fixup.UserInst) || isa<StoreInst>(Fixup.UserInst)) &&
+ !TTI.isFoldableMemAccessOffset(Fixup.UserInst, Offset))
+ NumBaseAdds++;

• SystemZ implementation of isFoldableMemAccessOffset() rewritten to also handle the case of fp-stores.

[jonpa]

Quentin, you approved this patch before, could you please take a quick look again so that my last changes look good to you? Sorry for confusion.

[qcolombet]

New rev LGTM as well!

Thanks,
-Quentin

[jonpa]

Commited as r278927.

include/llvm/Analysis/TargetTransformInfo.h

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;
 
+  unsigned increasedLSRFormulaCost(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
   /// by referencing its sub-register AX.
   bool isTruncateFree(Type *Ty1, Type *Ty2) const;
 
   /// \brief Return true if it is profitable to hoist instruction in the
   /// then/else to before if.
   bool isProfitableToHoist(Instruction *I) const;
 
   /// \brief Return true if this type is legal.
virtual bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV,
                                      unsigned AddrSpace) = 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 int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                    int64_t BaseOffset, bool HasBaseReg,
                                    int64_t Scale, unsigned AddrSpace) = 0;
+  virtual unsigned increasedLSRFormulaCost(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 enableAggressiveInterleaving(bool LoopHasReductions) = 0;
   virtual bool enableInterleavedAccessVectorization() = 0;
bool isLegalMaskedGather(Type *DataType) override {
     return Impl.isLegalMaskedGather(DataType);
   }
   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);
   }
+  unsigned increasedLSRFormulaCost(Instruction *I, int64_t Offset) override {
+    return Impl.increasedLSRFormulaCost(I, Offset);
+  }
   bool isTruncateFree(Type *Ty1, Type *Ty2) override {
     return Impl.isTruncateFree(Ty1, Ty2);
   }
   bool isProfitableToHoist(Instruction *I) override {
     return Impl.isProfitableToHoist(I);
   }
   bool isTypeLegal(Type *Ty) override { return Impl.isTypeLegal(Ty); }
   unsigned getJumpBufAlignment() override { return Impl.getJumpBufAlignment(); }

include/llvm/Analysis/TargetTransformInfoImpl.h

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;
   }
 
+  unsigned increasedLSRFormulaCost(Instruction *I, int64_t Offset) { return 0; }
+
   bool isTruncateFree(Type *Ty1, Type *Ty2) { return false; }
 
   bool isProfitableToHoist(Instruction *I) { return true; }
 
   bool isTypeLegal(Type *Ty) { return false; }
 
   unsigned getJumpBufAlignment() { return 0; }
 

include/llvm/CodeGen/BasicTTIImpl.h

int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
     TargetLoweringBase::AddrMode AM;
     AM.BaseGV = BaseGV;
     AM.BaseOffs = BaseOffset;
     AM.HasBaseReg = HasBaseReg;
     AM.Scale = Scale;
     return getTLI()->getScalingFactorCost(DL, AM, Ty, AddrSpace);
   }
 
+  unsigned increasedLSRFormulaCost(Instruction *I, int64_t Offset) {
+    return getTLI()->increasedLSRFormulaCost(I, Offset);
+  }
+
   bool isTruncateFree(Type *Ty1, Type *Ty2) {
     return getTLI()->isTruncateFree(Ty1, Ty2);
   }
 
   bool isProfitableToHoist(Instruction *I) {
     return getTLI()->isProfitableToHoist(I);
   }
 

include/llvm/Target/TargetLowering.h

public:
   virtual int getScalingFactorCost(const DataLayout &DL, const AddrMode &AM,
                                    Type *Ty, unsigned AS = 0) const {
     // Default: assume that any scaling factor used in a legal AM is free.
     if (isLegalAddressingMode(DL, AM, Ty, AS))
       return 0;
     return -1;
   }
 
+  virtual unsigned increasedLSRFormulaCost(Instruction *I, int64_t Offset) const {
+    return 0;
+  }
+
   /// 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.
   virtual bool isLegalICmpImmediate(int64_t) const {
     return true;
   }
 
   /// Return true if the specified immediate is legal add immediate, that is the

lib/Analysis/TargetTransformInfo.cpp

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;
 }
 
+unsigned TargetTransformInfo::increasedLSRFormulaCost(Instruction *I,
+                                                 int64_t Offset) const {
+  return TTIImpl->increasedLSRFormulaCost(I, Offset);
+}
+
 bool TargetTransformInfo::isTruncateFree(Type *Ty1, Type *Ty2) const {
   return TTIImpl->isTruncateFree(Ty1, Ty2);
 }
 
 bool TargetTransformInfo::isProfitableToHoist(Instruction *I) const {
   return TTIImpl->isProfitableToHoist(I);
 }
 

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 increasedLSRFormulaCost(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 *>
   getRegForInlineAsmConstraint(const TargetRegisterInfo *TRI,

lib/Target/SystemZ/SystemZISelLowering.cpp

 #include "SystemZCallingConv.h"
 #include "SystemZConstantPoolValue.h"
 #include "SystemZMachineFunctionInfo.h"
 #include "SystemZTargetMachine.h"
 #include "llvm/CodeGen/CallingConvLower.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetLoweringObjectFileImpl.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/IR/Intrinsics.h"
 #include <cctype>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "systemz-lower"
 
+
 namespace {
 // Represents a sequence for extracting a 0/1 value from an IPM result:
 // (((X ^ XORValue) + AddValue) >> Bit)
 struct IPMConversion {
   IPMConversion(unsigned xorValue, int64_t addValue, unsigned bit)
     : XORValue(xorValue), AddValue(addValue), Bit(bit) {}
 
   int64_t XORValue;
bool SystemZTargetLowering::isLegalAddressingMode(const DataLayout &DL,
   // 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;
 }
 
+unsigned SystemZTargetLowering::increasedLSRFormulaCost(Instruction *I,
+                                                        int64_t Offset) const {
+  if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
+    // There is little support for big offsets with FP / vector types.
+    if (!isUInt<12>(Offset) &&
+        (LI->getType()->isFloatingPointTy() || LI->getType()->isVectorTy()))
+      return 1;
+  }
+
+  return 0;
+}
+
 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/Transforms/Scalar/LoopStrengthReduce.cpp

 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
                                  const LSRUse &LU, const Formula &F);
 // Get the cost of the scaling factor used in F for LU.
 static unsigned getScalingFactorCost(const TargetTransformInfo &TTI,
                                      const LSRUse &LU, const Formula &F);
 
 namespace {
 
+/// An operand value in an instruction which is to be replaced with some
+/// equivalent, possibly strength-reduced, replacement.
+struct LSRFixup {
+  /// The instruction which will be updated.
+  Instruction *UserInst;
+
+  /// The operand of the instruction which will be replaced. The operand may be
+  /// used more than once; every instance will be replaced.
+  Value *OperandValToReplace;
+
+  /// If this user is to use the post-incremented value of an induction
+  /// variable, this variable is non-null and holds the loop associated with the
+  /// induction variable.
+  PostIncLoopSet PostIncLoops;
+
+  /// The index of the LSRUse describing the expression which this fixup needs,
+  /// minus an offset (below).
+  size_t LUIdx;
+
+  /// A constant offset to be added to the LSRUse expression.  This allows
+  /// multiple fixups to share the same LSRUse with different offsets, for
+  /// example in an unrolled loop.
+  int64_t Offset;
+
+  bool isUseFullyOutsideLoop(const Loop *L) const;
+
+  LSRFixup();
+
+  void print(raw_ostream &OS) const;
+  void dump() const;
+};
+
 /// This class is used to measure and compare candidate formulae.
 class Cost {
   /// TODO: Some of these could be merged. Also, a lexical ordering
   /// isn't always optimal.
   unsigned NumRegs;
   unsigned AddRecCost;
   unsigned NumIVMuls;
   unsigned NumBaseAdds;
#endif
   void RateFormula(const TargetTransformInfo &TTI,
                    const Formula &F,
                    SmallPtrSetImpl<const SCEV *> &Regs,
                    const DenseSet<const SCEV *> &VisitedRegs,
                    const Loop *L,
                    const SmallVectorImpl<int64_t> &Offsets,
                    ScalarEvolution &SE, DominatorTree &DT,
                    const LSRUse &LU,
+                   const SmallVector<LSRFixup, 16> &Fixups,
                    SmallPtrSetImpl<const SCEV *> *LoserRegs = nullptr);
 
   void print(raw_ostream &OS) const;
   void dump() const;
 
 private:
   void RateRegister(const SCEV *Reg,
                     SmallPtrSetImpl<const SCEV *> &Regs,
void Cost::RatePrimaryRegister(const SCEV *Reg,
   }
   if (Regs.insert(Reg).second) {
     RateRegister(Reg, Regs, L, SE, DT);
     if (LoserRegs && isLoser())
       LoserRegs->insert(Reg);
   }
 }
 
-void Cost::RateFormula(const TargetTransformInfo &TTI,
-                       const Formula &F,
-                       SmallPtrSetImpl<const SCEV *> &Regs,
-                       const DenseSet<const SCEV *> &VisitedRegs,
-                       const Loop *L,
-                       const SmallVectorImpl<int64_t> &Offsets,
-                       ScalarEvolution &SE, DominatorTree &DT,
-                       const LSRUse &LU,
-                       SmallPtrSetImpl<const SCEV *> *LoserRegs) {
-  assert(F.isCanonical() && "Cost is accurate only for canonical formula");
-  // Tally up the registers.
-  if (const SCEV *ScaledReg = F.ScaledReg) {
-    if (VisitedRegs.count(ScaledReg)) {
-      Lose();
-      return;
-    }
-    RatePrimaryRegister(ScaledReg, Regs, L, SE, DT, LoserRegs);
-    if (isLoser())
-      return;
-  }
-  for (const SCEV *BaseReg : F.BaseRegs) {
-    if (VisitedRegs.count(BaseReg)) {
-      Lose();
-      return;
-    }
-    RatePrimaryRegister(BaseReg, Regs, L, SE, DT, LoserRegs);
-    if (isLoser())
-      return;
-  }
-
-  // Determine how many (unfolded) adds we'll need inside the loop.
-  size_t NumBaseParts = F.getNumRegs();
-  if (NumBaseParts > 1)
-    // Do not count the base and a possible second register if the target
-    // allows to fold 2 registers.
-    NumBaseAdds +=
-        NumBaseParts - (1 + (F.Scale && isAMCompletelyFolded(TTI, LU, F)));
-  NumBaseAdds += (F.UnfoldedOffset != 0);
-
-  // Accumulate non-free scaling amounts.
-  ScaleCost += getScalingFactorCost(TTI, LU, F);
-
-  // Tally up the non-zero immediates.
-  for (int64_t O : Offsets) {
-    int64_t Offset = (uint64_t)O + F.BaseOffset;
-    if (F.BaseGV)
-      ImmCost += 64; // Handle symbolic values conservatively.
-                     // TODO: This should probably be the pointer size.
-    else if (Offset != 0)
-      ImmCost += APInt(64, Offset, true).getMinSignedBits();
-  }
-  assert(isValid() && "invalid cost");
-}
-
 /// Set this cost to a losing value.
 void Cost::Lose() {
   NumRegs = ~0u;
   AddRecCost = ~0u;
   NumIVMuls = ~0u;
   NumBaseAdds = ~0u;
   ImmCost = ~0u;
   SetupCost = ~0u;
if (SetupCost != 0)
     OS << ", plus " << SetupCost << " setup cost";
 }
 
 LLVM_DUMP_METHOD
 void Cost::dump() const {
   print(errs()); errs() << '\n';
 }
 
-namespace {
-
-/// An operand value in an instruction which is to be replaced with some
-/// equivalent, possibly strength-reduced, replacement.
-struct LSRFixup {
-  /// The instruction which will be updated.
-  Instruction *UserInst;
-
-  /// The operand of the instruction which will be replaced. The operand may be
-  /// used more than once; every instance will be replaced.
-  Value *OperandValToReplace;
-
-  /// If this user is to use the post-incremented value of an induction
-  /// variable, this variable is non-null and holds the loop associated with the
-  /// induction variable.
-  PostIncLoopSet PostIncLoops;
-
-  /// The index of the LSRUse describing the expression which this fixup needs,
-  /// minus an offset (below).
-  size_t LUIdx;
-
-  /// A constant offset to be added to the LSRUse expression.  This allows
-  /// multiple fixups to share the same LSRUse with different offsets, for
-  /// example in an unrolled loop.
-  int64_t Offset;
-
-  bool isUseFullyOutsideLoop(const Loop *L) const;
-
-  LSRFixup();
-
-  void print(raw_ostream &OS) const;
-  void dump() const;
-};
-
-}
-
 LSRFixup::LSRFixup()
   : UserInst(nullptr), OperandValToReplace(nullptr), LUIdx(~size_t(0)),
     Offset(0) {}
 
 /// Test whether this fixup always uses its value outside of the given loop.
 bool LSRFixup::isUseFullyOutsideLoop(const Loop *L) const {
   // PHI nodes use their value in their incoming blocks.
   if (const PHINode *PN = dyn_cast<PHINode>(UserInst)) {
public:
 
   KindType Kind;
   MemAccessTy AccessTy;
 
   SmallVector<int64_t, 8> Offsets;
   int64_t MinOffset;
   int64_t MaxOffset;
 
+  SmallVector<unsigned, 8> FixupIndexes;
+
   /// This records whether all of the fixups using this LSRUse are outside of
   /// the loop, in which case some special-case heuristics may be used.
   bool AllFixupsOutsideLoop;
 
   /// RigidFormula is set to true to guarantee that this use will be associated
   /// with a single formula--the one that initially matched. Some SCEV
   /// expressions cannot be expanded. This allows LSR to consider the registers
   /// used by those expressions without the need to expand them later after
public:
   void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses);
 
   void print(raw_ostream &OS) const;
   void dump() const;
 };
 
 }
 
+void Cost::RateFormula(const TargetTransformInfo &TTI,
+                       const Formula &F,
+                       SmallPtrSetImpl<const SCEV *> &Regs,
+                       const DenseSet<const SCEV *> &VisitedRegs,
+                       const Loop *L,
+                       const SmallVectorImpl<int64_t> &Offsets,
+                       ScalarEvolution &SE, DominatorTree &DT,
+                       const LSRUse &LU,
+                       const SmallVector<LSRFixup, 16> &Fixups,
+                       SmallPtrSetImpl<const SCEV *> *LoserRegs) {
+  assert(F.isCanonical() && "Cost is accurate only for canonical formula");
+  // Tally up the registers.
+  if (const SCEV *ScaledReg = F.ScaledReg) {
+    if (VisitedRegs.count(ScaledReg)) {
+      Lose();
+      return;
+    }
+    RatePrimaryRegister(ScaledReg, Regs, L, SE, DT, LoserRegs);
+    if (isLoser())
+      return;
+  }
+  for (const SCEV *BaseReg : F.BaseRegs) {
+    if (VisitedRegs.count(BaseReg)) {
+      Lose();
+      return;
+    }
+    RatePrimaryRegister(BaseReg, Regs, L, SE, DT, LoserRegs);
+    if (isLoser())
+      return;
+  }
+
+  // Determine how many (unfolded) adds we'll need inside the loop.
+  size_t NumBaseParts = F.getNumRegs();
+  if (NumBaseParts > 1)
+    // Do not count the base and a possible second register if the target
+    // allows to fold 2 registers.
+    NumBaseAdds +=
+        NumBaseParts - (1 + (F.Scale && isAMCompletelyFolded(TTI, LU, F)));
+  NumBaseAdds += (F.UnfoldedOffset != 0);
+
+  // Accumulate non-free scaling amounts.
+  ScaleCost += getScalingFactorCost(TTI, LU, F);
+
+  // Tally up the non-zero immediates.
+  for (int64_t O : Offsets) {
+    int64_t Offset = (uint64_t)O + F.BaseOffset;
+    if (F.BaseGV)
+      ImmCost += 64; // Handle symbolic values conservatively.
+                     // TODO: This should probably be the pointer size.
+    else if (Offset != 0)
+      ImmCost += APInt(64, Offset, true).getMinSignedBits();
+  }
+  assert(isValid() && "invalid cost");
+
+  // Allow target to penalize any Instruction+Offset combination.
+  for (auto &Idx : LU.FixupIndexes) {
+    const LSRFixup &Fixup = Fixups[Idx];
+    int64_t Offset = F.BaseOffset + Fixup.Offset;
+    NumBaseAdds += TTI.increasedLSRFormulaCost(Fixup.UserInst, Offset);
+  }
+}
+
 /// Test whether this use as a formula which has the same registers as the given
 /// formula.
 bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const {
   SmallVector<const SCEV *, 4> Key = F.BaseRegs;
   if (F.ScaledReg) Key.push_back(F.ScaledReg);
   // Unstable sort by host order ok, because this is only used for uniquifying.
   std::sort(Key.begin(), Key.end());
   return Uniquifier.count(Key);
if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst))
         Factors.insert(-1);
       }
 
     // Set up the initial formula for this use.
     std::pair<size_t, int64_t> P = getUse(S, Kind, AccessTy);
     LF.LUIdx = P.first;
     LF.Offset = P.second;
     LSRUse &LU = Uses[LF.LUIdx];
+    LU.FixupIndexes.push_back(Fixups.size() - 1);
     LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
     if (!LU.WidestFixupType ||
         SE.getTypeSizeInBits(LU.WidestFixupType) <
         SE.getTypeSizeInBits(LF.OperandValToReplace->getType()))
       LU.WidestFixupType = LF.OperandValToReplace->getType();
 
     // If this is the first use of this LSRUse, give it a formula.
     if (LU.Formulae.empty()) {
else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
         LSRFixup &LF = getNewFixup();
         LF.UserInst = const_cast<Instruction *>(UserInst);
         LF.OperandValToReplace = U;
         std::pair<size_t, int64_t> P = getUse(
             S, LSRUse::Basic, MemAccessTy());
         LF.LUIdx = P.first;
         LF.Offset = P.second;
         LSRUse &LU = Uses[LF.LUIdx];
+        LU.FixupIndexes.push_back(Fixups.size() - 1);
         LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
         if (!LU.WidestFixupType ||
             SE.getTypeSizeInBits(LU.WidestFixupType) <
             SE.getTypeSizeInBits(LF.OperandValToReplace->getType()))
           LU.WidestFixupType = LF.OperandValToReplace->getType();
         InsertSupplementalFormula(US, LU, LF.LUIdx);
         CountRegisters(LU.Formulae.back(), Uses.size() - 1);
         break;
for (size_t FIdx = 0, NumForms = LU.Formulae.size();
       // immediately, otherwise heuristics could choose them over others leading
       // to an unsatisfactory solution. Passing LoserRegs into RateFormula here
       // avoids the need to recompute this information across formulae using the
       // same bad AddRec. Passing LoserRegs is also essential unless we remove
       // the corresponding bad register from the Regs set.
       Cost CostF;
       Regs.clear();
       CostF.RateFormula(TTI, F, Regs, VisitedRegs, L, LU.Offsets, SE, DT, LU,
-                        &LoserRegs);
+                        Fixups, &LoserRegs);
       if (CostF.isLoser()) {
         // During initial formula generation, undesirable formulae are generated
         // by uses within other loops that have some non-trivial address mode or
         // use the postinc form of the IV. LSR needs to provide these formulae
         // as the basis of rediscovering the desired formula that uses an AddRec
         // corresponding to the existing phi. Once all formulae have been
         // generated, these initial losers may be pruned.
         DEBUG(dbgs() << "  Filtering loser "; F.print(dbgs());
for (size_t FIdx = 0, NumForms = LU.Formulae.size();
         if (P.second)
           continue;
 
         Formula &Best = LU.Formulae[P.first->second];
 
         Cost CostBest;
         Regs.clear();
         CostBest.RateFormula(TTI, Best, Regs, VisitedRegs, L, LU.Offsets, SE,
-                             DT, LU);
+                             DT, LU, Fixups);
         if (CostF < CostBest)
           std::swap(F, Best);
         DEBUG(dbgs() << "  Filtering out formula "; F.print(dbgs());
               dbgs() << "\n"
                         "    in favor of formula "; Best.print(dbgs());
               dbgs() << '\n');
       }
 #ifndef NDEBUG
if (NumReqRegsToFind != 0) {
       continue;
     }
 
     // Evaluate the cost of the current formula. If it's already worse than
     // the current best, prune the search at that point.
     NewCost = CurCost;
     NewRegs = CurRegs;
     NewCost.RateFormula(TTI, F, NewRegs, VisitedRegs, L, LU.Offsets, SE, DT,
-                        LU);
+                        LU, Fixups);
     if (NewCost < SolutionCost) {
       Workspace.push_back(&F);
       if (Workspace.size() != Uses.size()) {
         SolveRecurse(Solution, SolutionCost, Workspace, NewCost,
                      NewRegs, VisitedRegs);
         if (F.getNumRegs() == 1 && Workspace.size() == 1)
           VisitedRegs.insert(F.ScaledReg ? F.ScaledReg : F.BaseRegs[0]);
       } else {