[LSR] Drop LSR solution if it is less profitable than baseline

[eopXD]

Summary

The LSR may suggest less profitable transformation to the loop. This
patch adds check to prevent LSR from generating worse code than what
we already have.

Since LSR affects nearly all targets, the patch is guarded by the
option 'lsr-drop-solution' and default as disable for now.

The next step should be extending an TTI interface to allow target(s)
to enable this enhancememnt.

Debug log is added to remind user of such choice to skip the LSR
solution.

[Meinersbur]

Is it feasible to add a test case?

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3393

How can the baseline immediately become the loser?

3394

Since SCEV subexpressions can be reused by multiple instructions, doesn't this mean that this is overestimating the baseline cost?

5182

Instead of the const cast, would it be possible to make Cost::isLess accept a const object?

5183

Starting with newline?

[eopXD]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3393

I have encounter cases that the BaselineCost is updated to loser when compiling spec2k6 benchmarks. This if-statement is used for us to prevent assertion errors as RateFormula assumes the cost to not be a loser when called.

I have a patch (D125670) that is pretty simple to free us from using this if-statement? I think its pretty simple and we can land it first?

[eopXD]

@Meinersbur Thank you for the review. I'll update when pre-commit patches (D125670 and D126350) land.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3394

Yes you are right, we should prevent repeating RateFormula hen multiple IVStrideUse matches the same LU. Let me update my code.

5182

Created D126350.

[eopXD]

Rebase to latest main.

Don't include baseline cost when SCEV is not used inside the loop. (isUseFullyOutsideLoop(L) == false)

[eopXD]

Address review comments.

[eopXD]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3393

D125670 landed. Marking this thread as complete.

3394

Created DenseSet<int> VisitedLSRUse to take account for SCEV that is already calculated.

5182

D126350 landed, marking this thread as complete.

5183

Removed leading newline.

[eopXD]

Add test case.

[eopXD]

Update test case for debug log.

[eopXD]

Change:

• Drop solution when baseline solution is better
• Remove check for isLoser before calling RateFormula
• Minor adjustment to debug log

[eopXD]

Rebase to latest main.

[eopXD]

Use option to block this addition for now.

[eopXD]

Gentle ping, thank you :)

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

195

spell "solution" here.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3304

LUIdx is declared as size_t. Does this need to be DenseSet<size_t>?

[eopXD]

Address comments.

[eopXD]

Also separated debug message test case from the code gen test case.

[eopXD]

Add missing end-line in debug message.

[Meinersbur]

LGTM, and sorry for the delay.

Could you add a description to the commit message?

[eopXD]

Rebase to latest main.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

static cl::opt<unsigned> SetupCostDepthLimit(
     "lsr-setupcost-depth-limit", cl::Hidden, cl::init(7),
     cl::desc("The limit on recursion depth for LSRs setup cost"));
 
 static cl::opt<bool> AllowTerminatingConditionFoldingAfterLSR(
     "lsr-term-fold", cl::Hidden, cl::init(false),
     cl::desc("Attempt to replace primary IV with other IV."));
 
 STATISTIC(NumTermFold,
           "Number of terminating condition fold recognized and performed");
 
 #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;
class LSRInstance {
   /// Interesting factors between use strides.
   ///
   /// We explicitly use a SetVector which contains a SmallSet, instead of the
   /// default, a SmallDenseSet, because we need to use the full range of
   /// int64_ts, and there's currently no good way of doing that with
   /// SmallDenseSet.
   SetVector<int64_t, SmallVector<int64_t, 8>, SmallSet<int64_t, 8>> Factors;
 
+  /// Baseline cost for currently used SCEV. Drop the best solution by LSR if
+  /// the solution is not profitable.
+  Cost BaselineCost;
+
   /// Interesting use types, to facilitate truncation reuse.
   SmallSetVector<Type *, 4> Types;
 
   /// The list of interesting uses.
   mutable SmallVector<LSRUse, 16> Uses;
 
   /// Track which uses use which register candidates.
   RegUseTracker RegUses;
if (isa<PHINode>(Chain.tailUserInst())) {
     }
   }
 }
 
 void LSRInstance::CollectFixupsAndInitialFormulae() {
   BranchInst *ExitBranch = nullptr;
   bool SaveCmp = TTI.canSaveCmp(L, &ExitBranch, &SE, &LI, &DT, &AC, &TLI);
 
+  // For calculating InitialSolutionCost
+  SmallPtrSet<const SCEV *, 16> Regs;
+  DenseSet<const SCEV *> VisitedRegs;
+
   for (const IVStrideUse &U : IU) {
     Instruction *UserInst = U.getUser();
     // Skip IV users that are part of profitable IV Chains.
     User::op_iterator UseI =
         find(UserInst->operands(), U.getOperandValToReplace());
     assert(UseI != UserInst->op_end() && "cannot find IV operand");
     if (IVIncSet.count(UseI)) {
       LLVM_DEBUG(dbgs() << "Use is in profitable chain: " << **UseI << '\n');
for (const IVStrideUse &U : IU) {
     std::pair<size_t, int64_t> P = getUse(S, Kind, AccessTy);
     size_t LUIdx = P.first;
     int64_t Offset = P.second;
     LSRUse &LU = Uses[LUIdx];
 
     // Record the fixup.
     LSRFixup &LF = LU.getNewFixup();
     LF.UserInst = UserInst;
     LF.OperandValToReplace = U.getOperandValToReplace();
     LF.PostIncLoops = TmpPostIncLoops;
     LF.Offset = Offset;
     LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
 
+    // Create initial SCEV as Formula for baseline cost
+    if (!LF.isUseFullyOutsideLoop(L)) {
+      Formula F;
+      F.initialMatch(S, L, SE);
+      if (!BaselineCost.isLoser())
+        BaselineCost.RateFormula(F, Regs, VisitedRegs, LU);
+    }
+
     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()) {
       InsertInitialFormula(S, LU, LUIdx);
LLVM_DEBUG(dbgs() << "\n"
                Uses[i].print(dbgs());
                dbgs() << "\n"
                          "    ";
                Solution[i]->print(dbgs());
                dbgs() << '\n';
              });
 
   assert(Solution.size() == Uses.size() && "Malformed solution!");
+
+  if (!SolutionCost.isLess(const_cast<Cost &>(BaselineCost))) {
+    LLVM_DEBUG(dbgs() << "\n"
+                         "The baseline solution requires ";
+               BaselineCost.print(dbgs()); dbgs() << "\n";);
+
+    LLVM_DEBUG(
+        dbgs()
+        << "Baseline solution is more profitable than chosen solution.\n");
+    LLVM_DEBUG(dbgs() << "Dropping LSR chosen solution.\n");
+    Solution.clear();
+  }
 }
 
 /// Helper for AdjustInsertPositionForExpand. Climb up the dominator tree far as
 /// we can go while still being dominated by the input positions. This helps
 /// canonicalize the insert position, which encourages sharing.
 BasicBlock::iterator
 LSRInstance::HoistInsertPosition(BasicBlock::iterator IP,
                                  const SmallVectorImpl<Instruction *> &Inputs)

 LSRInstance::LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE,
                          DominatorTree &DT, LoopInfo &LI,
                          const TargetTransformInfo &TTI, AssumptionCache &AC,
                          TargetLibraryInfo &TLI, MemorySSAUpdater *MSSAU)
     : IU(IU), SE(SE), DT(DT), LI(LI), AC(AC), TLI(TLI), TTI(TTI), L(L),
       MSSAU(MSSAU), AMK(PreferredAddresingMode.getNumOccurrences() > 0
                             ? PreferredAddresingMode
                             : TTI.getPreferredAddressingMode(L, &SE)),
-      Rewriter(SE, L->getHeader()->getModule()->getDataLayout(), "lsr", false) {
+      Rewriter(SE, L->getHeader()->getModule()->getDataLayout(), "lsr", false),
+      BaselineCost(L, SE, TTI, AMK) {
   // If LoopSimplify form is not available, stay out of trouble.
   if (!L->isLoopSimplifyForm())
     return;
 
   // If there's no interesting work to be done, bail early.
   if (IU.empty()) return;
 
   // If there's too much analysis to be done, bail early. We won't be able to