Fix regressions cased by D29862

[evstupac]

Summary

The patch fix regressions in
Shootout-C++ matrix
and
spec2006/hmmer
caused by D29862.

[qcolombet]

Hi,

Could you explain what was the problem and how this patch addresses it?

Thanks,
-Quentin

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1080

Unrelated change?

4446

Why don't we have to update Regs anymore?

[evstupac]

Could you explain what was the problem and how this patch addresses it?

Sure, here is the case:

Use1 (Address):
{a} + {0,+,1} register num expectation 1 + 1/2
{a,+,1} register num expectation 1
Use2 (Address):
{b} + {0,+,1}
{b,+,1}
Use3 (ICmpZero):
-1024 + {0,+,1}

That way new method will select {a,+1} {b,+,1} and -1024 + {0,+,1} which is not optimal in terms of AddRecExprs (still optimal in terms of RegNum)

In Matrix test there are 32 Address uses like above. The expectation of {a} + {0,+,1} becomes very close 1, but still grater than 1.
The solution is simple - delete formulas in ICmpZero before Address. That way the optimal solution is selected (as {0,+,1} becomes unique).

lib/Transforms/Scalar/LoopStrengthReduce.cpp

4446

This is a kind of unrelated change (as it is redundant initially). We leave only 1 formula in each LSRUse, therfore we already select a solution (or no solution). That way we don't need to RecomputeRegs any more.
If we keep RecomputeRegs here we'll need to sort indexes instead of LSRUses as RecomputeRegs use LSRUse indexes.

[evstupac]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1080

No. This to to make compare function easier (compare enum values):
U1.Kind < U2.Kind

[evstupac]

Trying to fix the regressions I've inserted a check which uses Solution generated by NarrowSearchSpaceByDeletingCostlyFormulas() only if it's cost less than cost of regular Solution.
That way NarrowSearchSpaceByDeletingCostlyFormulas() can only decrease final Solution cost. But both matrix and hmmer regression were not resolved.
It turned out that NarrowSearchSpaceByDeletingCostlyFormulas() creates Solution with is better cost (using current cost model) for both cases.
Use of Insns in Cost model helps to resolve the issue.
Right now I see 3 ways to resolve this:

1. Accept current workaround.
2. Modify NarrowSearchSpaceByDeletingCostlyFormulas() to rely in Insns instead of Registers.
3. Change cost model to rely on Insns first and check which solution is better: regular or created by NarrowSearchSpaceByDeletingCostlyFormulas().

lib/Transforms/Scalar/LoopStrengthReduce.cpp

4392

We can sort Uses indexes here instead of sorting Uses. That way we'll avoid change on line 4435.

[evstupac]

How do you think which way we should follow?
Or we can leave regression as is as Solution Cost is better and therefore it is not a problem of newly implemented NarrowSearchSpaceByDeletingCostlyFormulas()?

lib/Transforms/Scalar/LoopStrengthReduce.cpp

 /// users of the same expression in common?
 class LSRUse {
   DenseSet<SmallVector<const SCEV *, 4>, UniquifierDenseMapInfo> Uniquifier;
 
 public:
   /// An enum for a kind of use, indicating what types of scaled and immediate
   /// operands it might support.
   enum KindType {
-    Basic,   ///< A normal use, with no folding.
-    Special, ///< A special case of basic, allowing -1 scales.
-    Address, ///< An address use; folding according to TargetLowering
-    ICmpZero ///< An equality icmp with both operands folded into one.
+    Basic,    ///< A normal use, with no folding.
+    ICmpZero, ///< An equality icmp with both operands folded into one.
+    Special,  ///< A special case of basic, allowing -1 scales.
+    Address   ///< An address use; folding according to TargetLowering
     // TODO: Add a generic icmp too?
   };
 
   typedef PointerIntPair<const SCEV *, 2, KindType> SCEVUseKindPair;
 
   KindType Kind;
   MemAccessTy AccessTy;
 

 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void LSRUse::dump() const {
   print(errs()); errs() << '\n';
 }
 #endif
 
+static bool LSRUseCompare (const LSRUse &U1, const LSRUse &U2) {
+  return (U1.Kind < U2.Kind) ||
+         (U1.Kind == U2.Kind && U1.Formulae.size() < U2.Formulae.size());
+}
+
 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
                                  LSRUse::KindType Kind, MemAccessTy AccessTy,
                                  GlobalValue *BaseGV, int64_t BaseOffset,
                                  bool HasBaseReg, int64_t Scale) {
   switch (Kind) {
   case LSRUse::Address:
     return TTI.isLegalAddressingMode(AccessTy.MemTy, BaseGV, BaseOffset,
                                      HasBaseReg, Scale, AccessTy.AddrSpace);
void LSRInstance::NarrowSearchSpaceByDeletingCostlyFormulas() {
   // Ok, we have too many of formulae on our hands to conveniently handle.
   // Use a rough heuristic to thin out the list.
 
   // Set of Regs wich will be 100% used in final solution.
   // Used in each formula of a solution (in example above this is reg(c)).
   // We can skip them in calculations.
   SmallPtrSet<const SCEV *, 4> UniqRegs;
   DEBUG(dbgs() << "The search space is too complex.\n");
+  // It is ok to sort Uses as we'll choose a solution in the function.
+  std::sort (Uses.begin(), Uses.end(), LSRUseCompare);
 
   // Map each register to probability of not selecting
   DenseMap <const SCEV *, float> RegNumMap;
   for (const SCEV *Reg : RegUses) {
     if (UniqRegs.count(Reg))
       continue;
     float PNotSel = 1;
     for (const LSRUse &LU : Uses) {
       if (!LU.Regs.count(Reg))
         continue;
       float P = LU.getNotSelectedProbability(Reg);
       if (P != 0.0)
         PNotSel *= P;
       else
         UniqRegs.insert(Reg);
     }
     RegNumMap.insert(std::make_pair(Reg, PNotSel));
   }
 
   DEBUG(dbgs() << "Narrowing the search space by deleting costly formulas\n");
 
   // Delete formulas where registers number expectation is high.
   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
     LSRUse &LU = Uses[LUIdx];
     // If nothing to delete - continue.
     if (LU.Formulae.size() < 2)
       continue;
     // This is temporary solution to test performance. Float should be
     // replaced with round independent type (based on integers) to avoid
     // different results for different target builds.
     float FMinRegNum = LU.Formulae[0].getNumRegs();
     float FMinARegNum = LU.Formulae[0].getNumRegs();
+    unsigned FMinBaseAdd = LU.Formulae[0].getNumRegs();
     size_t MinIdx = 0;
     for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) {
       Formula &F = LU.Formulae[i];
       float FRegNum = 0;
       float FARegNum = 0;
       for (const SCEV *BaseReg : F.BaseRegs) {
         if (UniqRegs.count(BaseReg))
           continue;
         FRegNum += RegNumMap[BaseReg] / LU.getNotSelectedProbability(BaseReg);
         if (isa<SCEVAddRecExpr>(BaseReg))
           FARegNum +=
               RegNumMap[BaseReg] / LU.getNotSelectedProbability(BaseReg);
       }
       if (const SCEV *ScaledReg = F.ScaledReg) {
         if (!UniqRegs.count(ScaledReg)) {
           FRegNum +=
               RegNumMap[ScaledReg] / LU.getNotSelectedProbability(ScaledReg);
           if (isa<SCEVAddRecExpr>(ScaledReg))
             FARegNum +=
                 RegNumMap[ScaledReg] / LU.getNotSelectedProbability(ScaledReg);
         }
       }
       if (FMinRegNum > FRegNum ||
-          (FMinRegNum == FRegNum && FMinARegNum > FARegNum)) {
+          (FMinRegNum == FRegNum &&
+           (FMinARegNum > FARegNum ||
+            (FMinARegNum == FARegNum && FMinBaseAdd > F.getNumRegs())))) {
         FMinRegNum = FRegNum;
         FMinARegNum = FARegNum;
+        FMinBaseAdd = F.getNumRegs();
         MinIdx = i;
       }
     }
     DEBUG(dbgs() << "  The formula "; LU.Formulae[MinIdx].print(dbgs());
           dbgs() << " with min reg num " << FMinRegNum << '\n');
     if (MinIdx != 0)
       std::swap(LU.Formulae[MinIdx], LU.Formulae[0]);
     while (LU.Formulae.size() != 1) {
       DEBUG(dbgs() << "  Deleting "; LU.Formulae.back().print(dbgs());
             dbgs() << '\n');
       LU.Formulae.pop_back();
     }
-    LU.RecomputeRegs(LUIdx, RegUses);
     assert(LU.Formulae.size() == 1 && "Should be exactly 1 min regs formula");
     Formula &F = LU.Formulae[0];
     DEBUG(dbgs() << "  Leaving only "; F.print(dbgs()); dbgs() << '\n');
     // When we choose the formula, the regs become unique.
     UniqRegs.insert(F.BaseRegs.begin(), F.BaseRegs.end());
     if (F.ScaledReg)
       UniqRegs.insert(F.ScaledReg);
   }
   DEBUG(dbgs() << "After pre-selection:\n";

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 %4, 1
-; CHECK: sub i64 [[TMP]], %tmp6
+; CHECK: [[REG:%[^ ]+]] = add i64 %tmp6, -1
+; CHECK: sub i64 [[REG]], %tmp5
 ; 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