[LSR] Narrow search space by filtering non-optimal formulae with the same ScaledReg and Scale.

[wmi]

Summary

When the formulae search space is huge, LSR uses a series of heuristic to keep pruning the search space until the number of possible solutions are within certain limit.

The big hammer of the series of heuristics is NarrowSearchSpaceByPickingWinnerRegs, which picks the register which is used by the most LSRUses and deletes the other formulae which don't use the register. This is a effective way to prune the search space, but quite often not a good way to keep the best solution. We saw cases before that the heuristic pruned the best formula candidate out of search space.

To relieve the problem, we introduce a new heuristic called NarrowSearchSpaceByFilterFormulaWithSameScaledReg. The basic idea is in order to reduce the search space while keeping the best formula, we want to keep as many formula with different Scale and ScaledReg as possible. That is because the central idea of LSR is to choose a group of loop induction variables and use those induction variables to represent LSRUses. An induction variable candidate is often represented by the Scale and ScaledReg in a formula. If we have more formulae with different ScaledReg and Scale to choose, we have better opportunity to find the best solution. That is why we believe pruning search space by only keeping the best formula with the same Scale and ScaledReg should be more effective than PickingWinnerReg. And we use two criteria to choose the best formula with the same Scale and ScaledReg. The first criteria is to select the formula using less non shared registers, and the second criteria is to select the formula with less cost got from RateFormula. The patch implements the heuristic before NarrowSearchSpaceByPickingWinnerRegs, which is the last resort.

Testing shows we get 1.8% and 2% on two internal benchmarks on x86. llvm nightly testsuite performance is neutral. We also tried lsr-exp-narrow and it didn't help on the two improved internal cases we saw.

[sanjoy]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

146

I'd s/scaledreg/scaled-reg/

4318

Just to be clear, this benefit here is that you can just look at the base regs and (cheaply) decide which one is better? If so, add a line in the description about that.

4338

I think the convention would be IsBetterThan.

I'd also add a one-liner on the direction of the relation you're computing ("return true if A is better than B").

4339

I'm being hyper pedantic here, but I suspect this will be "fewer" new registers.

4345

It's not clear to me why you need to use a floating point reciprocal here. Why not just count the total number of uses (as a integer) and compare that? Or is there some more subtle metric you're tracking that requires this reciprocal logic (if so please comment on that).

4355

Maybe the DenseSet can be declared at function scope and re-used in different invocations to isBetterThan? This is a worthwhile micro-optimization since DenseSet s are somewhat heavyweight.

4360

As far as I can tell, in this situation we're making an arbitrary choice when the register use count is the same and both the formulas have the same cost (we'll just pick the second one). Can we instead keep both the formulas when Cost does not give us a unambiguous signal?

4364

Let's call Any something more descriptive, like FormulaPruned.

[edit: I just saw that other parts of LSR also call this variable Any. I think those too should change, but given the "prior art" I'd be okay if you want to keep this named Any.]

[wmi]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

4318

The narrowing heuristic is to keep as many formulae with different Scale and ScaledReg pair as possible while narrowing the search space to be within limit. The benefit is that it is more likely to find out a better solution from a formulae set with more Scale and ScaledReg variations than picking the winner reg heuristic. Comments updated.

4345

Yeah I don't really need to use floating point. I change it to use integer.

4360

We uses the similar strategy in other places, like in FilterOutUndesirableDedicatedRegisters at the place: CostF.isLess(CostBest, TTI)). I think the key point here is to keep the formula set small while providing more induction variable choices for LSR solver, so making an arbitrary choice to reduce the formula set may not be too bad.

[wmi]

Address Sanjoy's comments.

[sanjoy]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

4352

Can we instead take the total number of uses of registers and FA.BaseRegs and FB.BaseRegs and compare them? That is:

int TotalUsesOfA = 0, TotalUsesOfB = 0;
for (const SCEV *Reg : FA.BaseRegs)
  TotalUsesOfA += RegUses.getUsedByIndices(Reg).count();
for (const SCEV *Reg : FB.BaseRegs)
  TotalUsesOfB += RegUses.getUsedByIndices(Reg).count();

if (TotalUsesOfA != TotalUsesOfB)
  return TotalUsesOfA > TotalUsesOfB;

Or does it have to exactly be the expression you're using?

4360

Sounds good.

test/Transforms/LoopStrengthReduce/X86/lsr-filtering-scaledreg.ll

7

Can you please clean up the names a bit here? Perhaps using metarenamer?

Also, are both the loops necessary to show the difference in behavior?

[wmi]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

4352

We don't want to choose the formula with the most sharing. What we expect is to have fewer registers. If a register is shared, we count it proportionally . That is why a shared register is better than a non-shared register.

test/Transforms/LoopStrengthReduce/X86/lsr-filtering-scaledreg.ll

7

metarenamer is a great tool. Thanks for the suggestion.

I reduce the test to some extend, but the second loop is still necessary to create a complex enough searching space.

[wmi]

Cleanup and reduce the testcase.

[sanjoy]

lgtm

test/Transforms/LoopStrengthReduce/X86/lsr-filtering-scaledreg.ll

7

I reduce the test to some extend, but the second loop is still necessary to create a complex enough searching space.

Sounds good!

[eastig]

test.ll3 KBDownload

test.good.ll3 KBDownload

test.bad.ll3 KBDownload

This patch caused regressions from 5% to 23% in two our internal benchmarks on Cortex-M23 and Cortex-M0+. I attached test.ll which is reduced from the benchmarks. I used LLVM revision 309830. 'test.good.ll' is a result when filtering is disabled. 'test.bad.ll' is a result when filtering is enabled.
Comparing them I can see that this optimization changes how an induction variable is changed. Originally it is incremented from 0 to 256. The optimization changes this into decrementing from 0 to -256. This induction variable is also used as an offset to memory. So to preserve this semantic conversion of the induction variable from a negative value to a positive value is inserted. This is lowered to additional instructions which causes performance regressions.

Could you please have a look at this issue?

Thanks,
Evgeny Astigeevich
The ARM Compiler Optimization team leader

[wmi]

In D34583#830286, @eastig wrote:

test.ll3 KBDownload

test.good.ll3 KBDownload

test.bad.ll3 KBDownload

This patch caused regressions from 5% to 23% in two our internal benchmarks on Cortex-M23 and Cortex-M0+. I attached test.ll which is reduced from the benchmarks. I used LLVM revision 309830. 'test.good.ll' is a result when filtering is disabled. 'test.bad.ll' is a result when filtering is enabled.
Comparing them I can see that this optimization changes how an induction variable is changed. Originally it is incremented from 0 to 256. The optimization changes this into decrementing from 0 to -256. This induction variable is also used as an offset to memory. So to preserve this semantic conversion of the induction variable from a negative value to a positive value is inserted. This is lowered to additional instructions which causes performance regressions.

Could you please have a look at this issue?

Thanks,
Evgeny Astigeevich
The ARM Compiler Optimization team leader

Hi Evgeny,

Thanks for providing the testcase.

It looks like an existing issue in LSR cost evaluation exposed by the patch. Actually, comparing the trace by adding -debug-only=loop-reduce, all the candidates choosen by LSR without filtering are kept in the candidate set after adding the filter patch. However filtering patch provides some more candidates interesting for LSR cost model to choose, and LSR chooses a different set of candidates in the final result which it thinks better (1 less base add) but actually not. We can see that in the trace:

LSR without the filtering patch:
The chosen solution requires 5 regs, with addrec cost 2, plus 2 base adds, plus 4 imm cost, plus 1 setup cost:

LSR Use: Kind=Address of i8 in addrspace(0), Offsets={0}, widest fixup type: i8*
  reg({%ptr1,+,256}<%for.cond6.preheader.us.i.i>) + 1*reg({0,+,1}<nuw><nsw><%for.body8.us.i.i>)
LSR Use: Kind=ICmpZero, Offsets={0}, widest fixup type: i32
  reg(256) + -1*reg({0,+,1}<nuw><nsw><%for.body8.us.i.i>)
LSR Use: Kind=Address of i32 in addrspace(0), Offsets={0}, widest fixup type: i32*
  reg(%c0.0103.us.i.i) + 4*reg({0,+,1}<nuw><nsw><%for.body8.us.i.i>)
LSR Use: Kind=Address of i32 in addrspace(0), Offsets={0,4}, widest fixup type: i32*
  reg({(-4 + %c1.0104.us.i.i)<nsw>,+,4}<nsw><%for.body8.us.i.i>)
LSR Use: Kind=Special, Offsets={0}, all-fixups-outside-loop, widest fixup type: i32*
  reg(%c0.0103.us.i.i)
LSR Use: Kind=Address of i32 in addrspace(0), Offsets={0}, widest fixup type: i32*
  reg(%c1.0104.us.i.i) + 4*reg({0,+,1}<nuw><nsw><%for.body8.us.i.i>) + imm(4)
LSR Use: Kind=Special, Offsets={0}, all-fixups-outside-loop, widest fixup type: i32*
  reg(%c1.0104.us.i.i)

LSR with the filtering patch:
The chosen solution requires 5 regs, with addrec cost 2, plus 1 base add, plus 4 imm cost, plus 1 setup cost:

LSR Use: Kind=Address of i8 in addrspace(0), Offsets={0}, widest fixup type: i8*
  reg({%ptr1,+,256}<%for.cond6.preheader.us.i.i>) + -1*reg({0,+,-1}<nw><%for.body8.us.i.i>)
LSR Use: Kind=ICmpZero, Offsets={0}, widest fixup type: i32
  reg(-256) + -1*reg({0,+,-1}<nw><%for.body8.us.i.i>)
LSR Use: Kind=Address of i32 in addrspace(0), Offsets={0}, widest fixup type: i32*
  reg(%c0.0103.us.i.i) + -4*reg({0,+,-1}<nw><%for.body8.us.i.i>)
LSR Use: Kind=Address of i32 in addrspace(0), Offsets={0,4}, widest fixup type: i32*
  reg({(4 + %c1.0104.us.i.i)<nsw>,+,4}<nsw><%for.body8.us.i.i>) + imm(-8)
LSR Use: Kind=Special, Offsets={0}, all-fixups-outside-loop, widest fixup type: i32*
  reg(%c0.0103.us.i.i)
LSR Use: Kind=Address of i32 in addrspace(0), Offsets={0}, widest fixup type: i32*
  reg({(4 + %c1.0104.us.i.i)<nsw>,+,4}<nsw><%for.body8.us.i.i>)
LSR Use: Kind=Special, Offsets={0}, all-fixups-outside-loop, widest fixup type: i32*
  reg(%c1.0104.us.i.i)

The real problem is that LSR has no idea about the cost of getting negative value. It thinks 4*reg({0,+,-1} and -4*reg({0,+,-1} have the same cost.

LSR Use: Kind=Address of i8 in addrspace(0), Offsets={0}, widest fixup type: i8*
  reg({%ptr1,+,256}<%for.cond6.preheader.us.i.i>) + -1*reg({0,+,-1}<nw><%for.body8.us.i.i>)
LSR Use: Kind=Address of i32 in addrspace(0), Offsets={0}, widest fixup type: i32*
  reg(%c0.0103.us.i.i) + -4*reg({0,+,-1}<nw><%for.body8.us.i.i>)

I will think about how to fix it.

Wei.

[eastig]

Thank you, Wei. Just let me know when you need help to test a fix.

lib/Transforms/Scalar/LoopStrengthReduce.cpp

static cl::opt<bool> InsnsCost(
   cl::desc("Add instruction count to a LSR cost model"));
 
 // Flag to choose how to narrow complex lsr solution
 static cl::opt<bool> LSRExpNarrow(
   "lsr-exp-narrow", cl::Hidden, cl::init(false),
   cl::desc("Narrow LSR complex solution using"
            " expectation of registers number"));
 
+// Flag to narrow search space by filtering non-optimal formulae with
+// the same ScaledReg and Scale.
+static cl::opt<bool> FilterSameScaledReg(
+    "lsr-filter-same-scaled-reg", cl::Hidden, cl::init(true),
+    cl::desc("Narrow LSR search space by filtering non-optimal formulae"
+             " with the same ScaledReg and Scale"));
+
 #ifndef NDEBUG
 // Stress test IV chain generation.
 static cl::opt<bool> StressIVChain(
   "stress-ivchain", cl::Hidden, cl::init(false),
   cl::desc("Stress test LSR IV chains"));
 #else
 static bool StressIVChain = false;
 #endif
class LSRInstance {
   void GenerateAllReuseFormulae();
 
   void FilterOutUndesirableDedicatedRegisters();
 
   size_t EstimateSearchSpaceComplexity() const;
   void NarrowSearchSpaceByDetectingSupersets();
   void NarrowSearchSpaceByCollapsingUnrolledCode();
   void NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters();
+  void NarrowSearchSpaceByFilterFormulaWithSameScaledReg();
   void NarrowSearchSpaceByDeletingCostlyFormulas();
   void NarrowSearchSpaceByPickingWinnerRegs();
   void NarrowSearchSpaceUsingHeuristics();
 
   void SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
                     Cost &SolutionCost,
                     SmallVectorImpl<const Formula *> &Workspace,
                     const Cost &CurCost,
if (EstimateSearchSpaceComplexity() >= ComplexityLimit) {
 
     FilterOutUndesirableDedicatedRegisters();
 
     DEBUG(dbgs() << "After pre-selection:\n";
           print_uses(dbgs()));
   }
 }
 
+/// If a LSRUse has multiple formulae with the same ScaledReg and Scale.
+/// Pick the best one and delete the others.
+/// This narrowing heuristic is to keep as many formulae with different
+/// Scale and ScaledReg pair as possible while narrowing the search space.
+/// The benefit is that it is more likely to find out a better solution
+/// from a formulae set with more Scale and ScaledReg variations than
+/// a formulae set with the same Scale and ScaledReg. The picking winner
+/// reg heurstic will often keep the formulae with the same Scale and
+/// ScaledReg and filter others, and we want to avoid that if possible.
+void LSRInstance::NarrowSearchSpaceByFilterFormulaWithSameScaledReg() {
+  if (EstimateSearchSpaceComplexity() < ComplexityLimit)
+    return;
+
+  DEBUG(dbgs() << "The search space is too complex.\n"
+                  "Narrowing the search space by choosing the best Formula "
+                  "from the Formulae with the same Scale and ScaledReg.\n");
+
+  // Map the "Scale * ScaledReg" pair to the best formula of current LSRUse.
+  typedef DenseMap<std::pair<const SCEV *, int64_t>, size_t> BestFormulaeTy;
+  BestFormulaeTy BestFormulae;
+#ifndef NDEBUG
+  bool ChangedFormulae = false;
+#endif
+  DenseSet<const SCEV *> VisitedRegs;
+  SmallPtrSet<const SCEV *, 16> Regs;
+
+  for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
+    LSRUse &LU = Uses[LUIdx];
+    DEBUG(dbgs() << "Filtering for use "; LU.print(dbgs()); dbgs() << '\n');
+
+    // Return true if Formula FA is better than Formula FB.
+    auto IsBetterThan = [&](Formula &FA, Formula &FB) {
+      // First we will try to choose the Formula with fewer new registers.
+      // For a register used by current Formula, the more the register is
+      // shared among LSRUses, the less we increase the register number
+      // counter of the formula.
+      size_t FARegNum = 0;
+      for (const SCEV *Reg : FA.BaseRegs) {
+        const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(Reg);
+        FARegNum += (NumUses - UsedByIndices.count() + 1);
+      }
+      size_t FBRegNum = 0;
+      for (const SCEV *Reg : FB.BaseRegs) {
+        const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(Reg);
+        FBRegNum += (NumUses - UsedByIndices.count() + 1);
+      }
+      if (FARegNum != FBRegNum)
+        return FARegNum < FBRegNum;
+
+      // If the new register numbers are the same, choose the Formula with
+      // less Cost.
+      Cost CostFA, CostFB;
+      Regs.clear();
+      CostFA.RateFormula(TTI, FA, Regs, VisitedRegs, L, SE, DT, LU);
+      Regs.clear();
+      CostFB.RateFormula(TTI, FB, Regs, VisitedRegs, L, SE, DT, LU);
+      return CostFA.isLess(CostFB, TTI);
+    };
+
+    bool Any = false;
+    for (size_t FIdx = 0, NumForms = LU.Formulae.size(); FIdx != NumForms;
+         ++FIdx) {
+      Formula &F = LU.Formulae[FIdx];
+      if (!F.ScaledReg)
+        continue;
+      auto P = BestFormulae.insert({{F.ScaledReg, F.Scale}, FIdx});
+      if (P.second)
+        continue;
+
+      Formula &Best = LU.Formulae[P.first->second];
+      if (IsBetterThan(F, Best))
+        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
+      ChangedFormulae = true;
+#endif
+      LU.DeleteFormula(F);
+      --FIdx;
+      --NumForms;
+      Any = true;
+    }
+    if (Any)
+      LU.RecomputeRegs(LUIdx, RegUses);
+
+    // Reset this to prepare for the next use.
+    BestFormulae.clear();
+  }
+
+  DEBUG(if (ChangedFormulae) {
+    dbgs() << "\n"
+              "After filtering out undesirable candidates:\n";
+    print_uses(dbgs());
+  });
+}
+
 /// The function delete formulas with high registers number expectation.
 /// Assuming we don't know the value of each formula (already delete
 /// all inefficient), generate probability of not selecting for each
 /// register.
 /// For example,
 /// Use1:
 ///  reg(a) + reg({0,+,1})
 ///  reg(a) + reg({-1,+,1}) + 1

 /// If there are an extraordinary number of formulae to choose from, use some
 /// rough heuristics to prune down the number of formulae. This keeps the main
 /// solver from taking an extraordinary amount of time in some worst-case
 /// scenarios.
 void LSRInstance::NarrowSearchSpaceUsingHeuristics() {
   NarrowSearchSpaceByDetectingSupersets();
   NarrowSearchSpaceByCollapsingUnrolledCode();
   NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters();
+  if (FilterSameScaledReg)
+    NarrowSearchSpaceByFilterFormulaWithSameScaledReg();
   if (LSRExpNarrow)
     NarrowSearchSpaceByDeletingCostlyFormulas();
   else
     NarrowSearchSpaceByPickingWinnerRegs();
 }
 
 /// This is the recursive solver.
 void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution,

test/CodeGen/X86/regalloc-reconcile-broken-hints.ll

-; RUN: llc < %s -o - -mtriple=x86_64-apple-macosx | FileCheck %s
+; RUN: llc -lsr-filter-same-scaled-reg=false < %s -o - -mtriple=x86_64-apple-macosx | FileCheck %s
 ; Test case for the recoloring of broken hints.
 ; This is tricky to have something reasonably small to kick this optimization since
 ; it requires that spliting and spilling occur.
 ; The bottom line is that this test case is fragile.
 ; This was reduced from the make_list function from the llvm-testsuite:
 ; SingleSource/Benchmarks/McGill/chomp.c
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"

test/Transforms/LoopStrengthReduce/2013-01-14-ReuseCast.ll

 ; RUN: opt -loop-reduce -S < %s | FileCheck %s
 ;
 ; LTO of clang, which mistakenly uses no TargetLoweringInfo, causes a
 ; miscompile. ReuseOrCreateCast replace ptrtoint operand with undef.
 ; Reproducing the miscompile requires no triple, hence no "TTI".
 ; rdar://13007381
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Verify that nothing uses the "dead" ptrtoint from "undef".
 ; CHECK-LABEL: @VerifyDiagnosticConsumerTest(
 ; CHECK: bb:
 ; "dead" ptrpoint not emitted (or dead code eliminated) with
 ; current LSR cost model.
 ; CHECK-NOT: = ptrtoint i8* undef to i64
 ; CHECK: .lr.ph
-; CHECK: [[TMP:%[^ ]+]] = add i64 %tmp5, 1
-; CHECK: sub i64 [[TMP]], %tmp6
+; CHECK: [[TMP:%[^ ]+]] = add i64 %tmp{{[0-9]+}}, -1
+; CHECK: sub i64 [[TMP]], %tmp{{[0-9]+}}
 ; CHECK: ret void
 define void @VerifyDiagnosticConsumerTest() unnamed_addr nounwind uwtable align 2 {
 bb:
   %tmp3 = call i8* @getCharData() nounwind
   %tmp4 = call i8* @getCharData() nounwind
   %tmp5 = ptrtoint i8* %tmp4 to i64
   %tmp6 = ptrtoint i8* %tmp3 to i64
   %tmp7 = sub i64 %tmp5, %tmp6

test/Transforms/LoopStrengthReduce/X86/lsr-filtering-scaledreg.ll

+; RUN: opt < %s -loop-reduce -lsr-filter-same-scaled-reg=true -mtriple=x86_64-unknown-linux-gnu -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%class.A = type { i8, i8, [5 x i32], i64, i64, i64 }
+%class.ZippyScatteredWriter = type { i8, i8*, i8* }
+@e = local_unnamed_addr global %class.A { i8 0, i8 0, [5 x i32] zeroinitializer, i64 1, i64 0, i64 1 }, align 8
+@f = local_unnamed_addr global %class.ZippyScatteredWriter* null, align 8
+declare void @_ZN20ZippyScatteredWriter5m_fn2Ev(%class.ZippyScatteredWriter*) local_unnamed_addr
+
+define void @foo() local_unnamed_addr {
+entry:
+  %tmp = load %class.ZippyScatteredWriter*, %class.ZippyScatteredWriter** @f, align 8
+  %op_ptr_.i.i = getelementptr inbounds %class.ZippyScatteredWriter, %class.ZippyScatteredWriter* %tmp, i64 0, i32 1
+  %sub.ptr.rhs.cast.i.i = ptrtoint %class.ZippyScatteredWriter* %tmp to i64
+  %op_limit_.i.i = getelementptr inbounds %class.ZippyScatteredWriter, %class.ZippyScatteredWriter* %tmp, i64 0, i32 2
+  br label %for.cond.i
+
+for.cond.i:                                       ; preds = %_ZN20ZippyScatteredWriter5m_fn3Emm.exit.i, %entry
+  %tmp1 = load i64, i64* getelementptr inbounds (%class.A, %class.A* @e, i64 0, i32 3), align 8
+  %and.i = and i64 %tmp1, 1792
+  %tmp2 = load i64, i64* getelementptr inbounds (%class.A, %class.A* @e, i64 0, i32 4), align 8
+  %add.i = add i64 %and.i, %tmp2
+  %tmp3 = load i64, i64* getelementptr inbounds (%class.A, %class.A* @e, i64 0, i32 5), align 8
+  %tmp4 = load i8*, i8** %op_ptr_.i.i, align 8
+  %add.ptr.i.i = getelementptr inbounds i8, i8* %tmp4, i64 %tmp3
+  %sub.i.i = add i64 %add.i, -1
+  %sub.ptr.lhs.cast.i.i = ptrtoint i8* %tmp4 to i64
+  %sub.ptr.sub.i.i = sub i64 %sub.ptr.lhs.cast.i.i, %sub.ptr.rhs.cast.i.i
+  %cmp.i.i = icmp ult i64 %sub.i.i, %sub.ptr.sub.i.i
+  br i1 %cmp.i.i, label %land.rhs.i.i, label %_ZN20ZippyScatteredWriter5m_fn3Emm.exit.i
+
+land.rhs.i.i:                                     ; preds = %for.cond.i
+  %tmp5 = load i8*, i8** %op_limit_.i.i, align 8
+  %cmp3.i.i = icmp ugt i8* %add.ptr.i.i, %tmp5
+  br i1 %cmp3.i.i, label %_ZN20ZippyScatteredWriter5m_fn3Emm.exit.i, label %if.then.i.i
+
+if.then.i.i:                                      ; preds = %land.rhs.i.i
+  %idx.neg.i.i = sub i64 0, %add.i
+  %add.ptr5.i.i = getelementptr inbounds i8, i8* %tmp4, i64 %idx.neg.i.i
+  %sub.ptr.rhs.cast.i.i.i = ptrtoint i8* %add.ptr5.i.i to i64
+  %tmp6 = sub i64 0, %sub.ptr.rhs.cast.i.i.i
+  %add.ptr.i.i.i = inttoptr i64 %tmp6 to i8*
+  %add.ptr1.i.i.i = getelementptr inbounds i8, i8* %tmp5, i64 -6
+  br label %while.cond.i.i.i
+
+; Without filtering non-optimal formulae with the same ScaledReg and Scale, the strategy
+; to narrow LSR search space by picking winner reg will generate one lsr.iv and unoptimal
+; result.
+; CHECK-LABEL: @foo(
+; CHECK: while.cond.i.i.i:
+; CHECK-NOT: %lsr.iv = phi i64
+; CHECK-NEXT: %p1.addr.0.i.i.i = phi i8*
+; CHECK-NEXT: %b.0.i.i.i = phi i8*
+
+while.cond.i.i.i:                                 ; preds = %while.body.i.i.i, %if.then.i.i
+  %p1.addr.0.i.i.i = phi i8* [ %add.ptr5.i.i, %if.then.i.i ], [ %add.ptr4.i.i.i, %while.body.i.i.i ]
+  %b.0.i.i.i = phi i8* [ %add.ptr.i.i.i, %if.then.i.i ], [ %add.ptr5.i.i.i, %while.body.i.i.i ]
+  %cmp.i.i.i = icmp ugt i8* %b.0.i.i.i, %add.ptr1.i.i.i
+  br i1 %cmp.i.i.i, label %while.end.i.i.i, label %while.body.i.i.i
+
+while.body.i.i.i:                                 ; preds = %while.cond.i.i.i
+  %a.sroa.0.0..sroa_cast2.i.i.i.i = bitcast i8* %p1.addr.0.i.i.i to i64*
+  %a.sroa.0.0.copyload.i.i.i.i = load i64, i64* %a.sroa.0.0..sroa_cast2.i.i.i.i, align 1
+  %a.sroa.0.0..sroa_cast3.i.i.i.i = bitcast i8* %b.0.i.i.i to i64*
+  store i64 %a.sroa.0.0.copyload.i.i.i.i, i64* %a.sroa.0.0..sroa_cast3.i.i.i.i, align 1
+  %add.ptr2.i.i.i = getelementptr inbounds i8, i8* %p1.addr.0.i.i.i, i64 8
+  %add.ptr3.i.i.i = getelementptr inbounds i8, i8* %b.0.i.i.i, i64 8
+  %a.sroa.0.0..sroa_cast2.i39.i.i.i = bitcast i8* %add.ptr2.i.i.i to i64*
+  %a.sroa.0.0.copyload.i40.i.i.i = load i64, i64* %a.sroa.0.0..sroa_cast2.i39.i.i.i, align 1
+  %a.sroa.0.0..sroa_cast3.i41.i.i.i = bitcast i8* %add.ptr3.i.i.i to i64*
+  store i64 %a.sroa.0.0.copyload.i40.i.i.i, i64* %a.sroa.0.0..sroa_cast3.i41.i.i.i, align 1
+  %add.ptr4.i.i.i = getelementptr inbounds i8, i8* %p1.addr.0.i.i.i, i64 16
+  %add.ptr5.i.i.i = getelementptr inbounds i8, i8* %b.0.i.i.i, i64 16
+  %cmp6.i.i.i = icmp ult i8* %add.ptr5.i.i.i, %add.ptr.i.i
+  br i1 %cmp6.i.i.i, label %while.cond.i.i.i, label %_Z15IncrementalCopyPKcPcS1_.exit.i.i.loopexit30
+
+while.end.i.i.i:                                  ; preds = %while.cond.i.i.i
+  %add.ptr8.i.i.i = getelementptr inbounds i8, i8* %tmp5, i64 -8
+  %cmp9.i.i.i = icmp ugt i8* %b.0.i.i.i, %add.ptr8.i.i.i
+  br i1 %cmp9.i.i.i, label %if.end16.i.i.i, label %if.then13.i.i.i
+
+if.then13.i.i.i:                                  ; preds = %while.end.i.i.i
+  %a.sroa.0.0..sroa_cast2.i42.i.i.i = bitcast i8* %p1.addr.0.i.i.i to i64*
+  %a.sroa.0.0.copyload.i43.i.i.i = load i64, i64* %a.sroa.0.0..sroa_cast2.i42.i.i.i, align 1
+  %a.sroa.0.0..sroa_cast3.i44.i.i.i = bitcast i8* %b.0.i.i.i to i64*
+  store i64 %a.sroa.0.0.copyload.i43.i.i.i, i64* %a.sroa.0.0..sroa_cast3.i44.i.i.i, align 1
+  %add.ptr14.i.i.i = getelementptr inbounds i8, i8* %p1.addr.0.i.i.i, i64 8
+  %add.ptr15.i.i.i = getelementptr inbounds i8, i8* %b.0.i.i.i, i64 8
+  br label %if.end16.i.i.i
+
+if.end16.i.i.i:                                   ; preds = %if.then13.i.i.i, %while.end.i.i.i
+  %p1.addr.1.i.i.i = phi i8* [ %add.ptr14.i.i.i, %if.then13.i.i.i ], [ %p1.addr.0.i.i.i, %while.end.i.i.i ]
+  %b.1.i.i.i = phi i8* [ %add.ptr15.i.i.i, %if.then13.i.i.i ], [ %b.0.i.i.i, %while.end.i.i.i ]
+  %b.1.i.i.i13 = ptrtoint i8* %b.1.i.i.i to i64
+  %cmp4.i.i.i.i = icmp ult i8* %b.1.i.i.i, %add.ptr.i.i
+  br i1 %cmp4.i.i.i.i, label %while.body.i.i.i.i.preheader, label %_Z15IncrementalCopyPKcPcS1_.exit.i.i
+
+while.body.i.i.i.i.preheader:                     ; preds = %if.end16.i.i.i
+  %tmp7 = sub i64 %tmp3, %b.1.i.i.i13
+  %scevgep = getelementptr i8, i8* %tmp4, i64 %tmp7
+  %exitcount.ptrcnt.to.int = ptrtoint i8* %scevgep to i64
+  %min.iters.check = icmp ult i8* %scevgep, inttoptr (i64 32 to i8*)
+  br i1 %min.iters.check, label %while.body.i.i.i.i.preheader29, label %min.iters.checked
+
+min.iters.checked:                                ; preds = %while.body.i.i.i.i.preheader
+  %n.vec = and i64 %exitcount.ptrcnt.to.int, -32
+  %cmp.zero = icmp eq i64 %n.vec, 0
+  br i1 %cmp.zero, label %while.body.i.i.i.i.preheader29, label %vector.memcheck
+
+vector.memcheck:                                  ; preds = %min.iters.checked
+  %tmp8 = sub i64 %tmp3, %b.1.i.i.i13
+  %scevgep14 = getelementptr i8, i8* %tmp4, i64 %tmp8
+  %scevgep1415 = ptrtoint i8* %scevgep14 to i64
+  %scevgep16 = getelementptr i8, i8* %p1.addr.1.i.i.i, i64 %scevgep1415
+  %bound0 = icmp ult i8* %b.1.i.i.i, %scevgep16
+  %bound1 = icmp ult i8* %p1.addr.1.i.i.i, %add.ptr.i.i
+  %memcheck.conflict = and i1 %bound0, %bound1
+  %ind.end = getelementptr i8, i8* %p1.addr.1.i.i.i, i64 %n.vec
+  %ind.end18 = getelementptr i8, i8* %b.1.i.i.i, i64 %n.vec
+  br i1 %memcheck.conflict, label %while.body.i.i.i.i.preheader29, label %vector.body.preheader
+
+vector.body.preheader:                            ; preds = %vector.memcheck
+  %tmp9 = add i64 %n.vec, -32
+  %tmp10 = lshr exact i64 %tmp9, 5
+  %tmp11 = add nuw nsw i64 %tmp10, 1
+  %xtraiter = and i64 %tmp11, 3
+  %tmp12 = icmp ult i64 %tmp9, 96
+  br i1 %tmp12, label %_Z15IncrementalCopyPKcPcS1_.exit.i.i.loopexit, label %vector.body.preheader.new
+
+vector.body.preheader.new:                        ; preds = %vector.body.preheader
+  %cmp.n = icmp eq i64 %n.vec, %exitcount.ptrcnt.to.int
+  br i1 %cmp.n, label %_Z15IncrementalCopyPKcPcS1_.exit.i.i, label %while.body.i.i.i.i.preheader29
+
+while.body.i.i.i.i.preheader29:                   ; preds = %vector.body.preheader.new, %vector.memcheck, %min.iters.checked, %while.body.i.i.i.i.preheader
+  %p1.addr.06.i.i.i.i.ph = phi i8* [ %ind.end, %vector.body.preheader.new ], [ %p1.addr.1.i.i.i, %while.body.i.i.i.i.preheader ], [ %p1.addr.1.i.i.i, %min.iters.checked ], [ %p1.addr.1.i.i.i, %vector.memcheck ]
+  %p2.addr.05.i.i.i.i.ph = phi i8* [ %ind.end18, %vector.body.preheader.new ], [ %b.1.i.i.i, %while.body.i.i.i.i.preheader ], [ %b.1.i.i.i, %min.iters.checked ], [ %b.1.i.i.i, %vector.memcheck ]
+  br label %while.body.i.i.i.i
+
+while.body.i.i.i.i:                               ; preds = %while.body.i.i.i.i, %while.body.i.i.i.i.preheader29
+  %p1.addr.06.i.i.i.i = phi i8* [ %incdec.ptr.i.i.i.i, %while.body.i.i.i.i ], [ %p1.addr.06.i.i.i.i.ph, %while.body.i.i.i.i.preheader29 ]
+  %p2.addr.05.i.i.i.i = phi i8* [ %incdec.ptr1.i.i.i.i, %while.body.i.i.i.i ], [ %p2.addr.05.i.i.i.i.ph, %while.body.i.i.i.i.preheader29 ]
+  %incdec.ptr.i.i.i.i = getelementptr inbounds i8, i8* %p1.addr.06.i.i.i.i, i64 1
+  %t43 = load i8, i8* %p1.addr.06.i.i.i.i, align 1
+  %incdec.ptr1.i.i.i.i = getelementptr inbounds i8, i8* %p2.addr.05.i.i.i.i, i64 1
+  store i8 %t43, i8* %p2.addr.05.i.i.i.i, align 1
+  %exitcond.i.i.i.i = icmp eq i8* %incdec.ptr1.i.i.i.i, %add.ptr.i.i
+  br i1 %exitcond.i.i.i.i, label %_Z15IncrementalCopyPKcPcS1_.exit.i.i.loopexit, label %while.body.i.i.i.i
+
+_Z15IncrementalCopyPKcPcS1_.exit.i.i.loopexit:    ; preds = %while.body.i.i.i.i, %vector.body.preheader
+  br label %_Z15IncrementalCopyPKcPcS1_.exit.i.i
+
+_Z15IncrementalCopyPKcPcS1_.exit.i.i.loopexit30:  ; preds = %while.body.i.i.i
+  br label %_Z15IncrementalCopyPKcPcS1_.exit.i.i
+
+_Z15IncrementalCopyPKcPcS1_.exit.i.i:             ; preds = %_Z15IncrementalCopyPKcPcS1_.exit.i.i.loopexit30, %_Z15IncrementalCopyPKcPcS1_.exit.i.i.loopexit, %vector.body.preheader.new, %if.end16.i.i.i
+  store i8* %add.ptr.i.i, i8** %op_ptr_.i.i, align 8
+  br label %_ZN20ZippyScatteredWriter5m_fn3Emm.exit.i
+
+_ZN20ZippyScatteredWriter5m_fn3Emm.exit.i:        ; preds = %_Z15IncrementalCopyPKcPcS1_.exit.i.i, %land.rhs.i.i, %for.cond.i
+  tail call void @_ZN20ZippyScatteredWriter5m_fn2Ev(%class.ZippyScatteredWriter* nonnull %tmp)
+  br label %for.cond.i
+}