[LSR] Skip transformation if the cost of no LSR is cheaper than the best solution selected

[junbuml]

Summary

I'm posting this to get any early feedback. Please let me know if this make sense.

TODO: tests should be added.

[junbuml]

With this change, I observed %2 performance improvement in spec2006/astar. This is a pretty simple try. Please let me know any feedback.

[qcolombet]

Hi Jun,

Instead of having a new method, can’t we consider this solution as part of the normal processing?
That way, if this is the best solution, we would naturally get it.

Cheers,
-Quentin

[junbuml]

Instead of having a new method, can’t we consider this solution as part of the normal processing?
That way, if this is the best solution, we would naturally get it.

Hi Quentin,

I tried to add the original formula used in IsNothingCheaperThanBestSolution() as candidates to allow SolveRecurse() pick them during normal process. However, with that try, I found the formula from original IR was failed to be added in LSRUse::InsertFormula() because they overlapped with the initial formula created in CollectFixupsAndInitialFormulae().

Instead of adding more candidate and expanding search space in SolveRecurse(), we may also want to have a separate function which only finds the cost from original IR.

[qcolombet]

Hi Jun,

The thing with LSR is that it is already complex enough that if we can avoid adding more separate paths I think it is best.

I found the formula from original IR was failed to be added in LSRUse::InsertFormula() because they overlapped with the initial formula created in CollectFixupsAndInitialFormulae().

That is an interesting piece of information!
Why is best better than this one but not better than the one we add with IsNothingCheaperThanBestSolution?

Cheers,
-Quentin

[sanjoy]

Looks stale, please add me back if you want to revive this.

[junbuml]

The initial cost I meant here was the cost before the post-increment normalization, and I skipped rewriting for the best solution selected from the post-inc transformed candidates if the initial cost is cheaper than the best solution. However, I found very fundamental cases were not handled by skipping rewriting.

lib/Transforms/Scalar/LoopStrengthReduce.cpp

class LSRInstance {
   void SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
                     Cost &SolutionCost,
                     SmallVectorImpl<const Formula *> &Workspace,
                     const Cost &CurCost,
                     const SmallPtrSet<const SCEV *, 16> &CurRegs,
                     DenseSet<const SCEV *> &VisitedRegs) const;
   void Solve(SmallVectorImpl<const Formula *> &Solution) const;
 
+  bool IsNothingCheaperThanBestSolution(Cost BestCost) const;
+
   BasicBlock::iterator
     HoistInsertPosition(BasicBlock::iterator IP,
                         const SmallVectorImpl<Instruction *> &Inputs) const;
   BasicBlock::iterator
     AdjustInsertPositionForExpand(BasicBlock::iterator IP,
                                   const LSRFixup &LF,
                                   const LSRUse &LU,
                                   SCEVExpander &Rewriter) const;

 /// scenarios.
 void LSRInstance::NarrowSearchSpaceUsingHeuristics() {
   NarrowSearchSpaceByDetectingSupersets();
   NarrowSearchSpaceByCollapsingUnrolledCode();
   NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters();
   NarrowSearchSpaceByPickingWinnerRegs();
 }
 
+bool LSRInstance::IsNothingCheaperThanBestSolution(Cost BestCost) const {
+  DenseSet<const SCEV *> VisitedRegs;
+  SmallPtrSet<const SCEV *, 16> Regs;
+  Cost BaseCost;
+
+  for (const LSRFixup &LF : Fixups) {
+    const SCEV *S = SE.getSCEV(LF.OperandValToReplace);
+    Formula F;
+    F.initialMatch(S, L, SE);
+
+    const LSRUse &LU = Uses[LF.LUIdx];
+    BaseCost.RateFormula(TTI, F, Regs, VisitedRegs, L, LU.Offsets, SE, DT, LU);
+    if (BestCost < BaseCost)
+      return false;
+  }
+  return (BaseCost < BestCost);
+}
+
+
 /// This is the recursive solver.
 void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
                                Cost &SolutionCost,
                                SmallVectorImpl<const Formula *> &Workspace,
                                const Cost &CurCost,
                                const SmallPtrSet<const SCEV *, 16> &CurRegs,
                                DenseSet<const SCEV *> &VisitedRegs) const {
   // Some ideas:
void LSRInstance::Solve(SmallVectorImpl<const Formula *> &Solution) const {
   Workspace.reserve(Uses.size());
 
   // SolveRecurse does all the work.
   SolveRecurse(Solution, SolutionCost, Workspace, CurCost,
                CurRegs, VisitedRegs);
   if (Solution.empty()) {
     DEBUG(dbgs() << "\nNo Satisfactory Solution\n");
     return;
+  } else if (IsNothingCheaperThanBestSolution(SolutionCost)) {
+    DEBUG(dbgs() << "\nThe best solution is not cheaper than no LSR\n");
+    Solution.clear();
+    return;
   }
 
   // Ok, we've now made all our decisions.
   DEBUG(dbgs() << "\n"
                   "The chosen solution requires "; SolutionCost.print(dbgs());
         dbgs() << ":\n";
         for (size_t i = 0, e = Uses.size(); i != e; ++i) {
           dbgs() << "  ";