[NFC][SCEV] Piping to pass new SCEVCheapExpansionBudget option into SCEVExpander::isHighCostExpansionHelper()

[lebedev.ri]

Summary

In future patches`SCEVExpander::isHighCostExpansionHelper()` will respect the budget allocated by performing TTI cost modelling.
This is a fully NFC patch to make things reviewable.

[lebedev.ri]

NFC, isHighCostExpansionHelper() should take BudgetRemaining by reference.

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

186

Should it be unsigned?

331

Please make all budgets either signed or unsigned. This should be consistent.

[lebedev.ri]

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

186

Absolutely not.
For signed, it is obvious how to check that we've out of budget (it became negative),
while for unsigned i would need to be checking the remaining budget vs it's adjustment.

[lebedev.ri]

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

331

There are two functions here: isHighCostExpansionHelper()
and isHighCostExpansion().

The helper is internal and self-recursive, and must have *signed*
budget parameter since it makes logic much better.

The isHighCostExpansion() is public, and is normally called with
just the SCEVCheapExpansionBudget param. I'm not sure it makes
much sense in accepting that param as signed,
because what would negative budget mean?

I suppose i could rename scev-cheap-expansion-budget param
to scev-cheap-expansion-threshold so all budgets are signed,
if that is better?

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

331

And how it's going to work if the user specifies bugdet greater than max signed int?

[lebedev.ri]

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

331

And if it's signed, what happens if the specified value overflows during it's multiplication by TargetTransformInfo::TCC_Basic?

All these options are by definition internal, non-public. I'm not very sure
how much time we want to spend ensuring that one can't use it as a footgun.
Besides, this merely models preexisting practice:
https://github.com/llvm/llvm-project/blob/a3d489e87e8243bdb0eff947a38006b039dff8c0/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L93-L105
https://github.com/llvm/llvm-project/blob/a3d489e87e8243bdb0eff947a38006b039dff8c0/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2017
https://github.com/llvm/llvm-project/blob/a3d489e87e8243bdb0eff947a38006b039dff8c0/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2334-L2335
https://github.com/llvm/llvm-project/blob/a3d489e87e8243bdb0eff947a38006b039dff8c0/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L3011-L3012

[lebedev.ri]

Rebased, NFC.
Let me know if/how this should be hardened.

[mkazantsev]

Ok, thanks for clarification. Let them shoot their legs then. :) LGTM

[lebedev.ri]

In D73705#1866682, @mkazantsev wrote:

Ok, thanks for clarification. Let them shoot their legs then. :) LGTM

Thank you for the review!
To be noted, i'm not vehemently opposed to hardening, but not before
there is a clear idea what we should be actually doing for the undefined cases.

[lebedev.ri]

Rebased, NFC.

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Analysis/TargetFolder.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/CommandLine.h"
 
 namespace llvm {
-  class TargetTransformInfo;
+  extern cl::opt<unsigned> SCEVCheapExpansionBudget;
 
   /// Return true if the given expression is safe to expand in the sense that
   /// all materialized values are safe to speculate anywhere their operands are
   /// defined.
   bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE);
 
   /// Return true if the given expression is safe to expand in the sense that
   /// all materialized values are defined and safe to speculate at the specified
#endif
     }
 
     /// Return true for expressions that may incur non-trivial cost to evaluate
     /// at runtime.
     ///
     /// At is an optional parameter which specifies point in code where user is
     /// going to expand this expression. Sometimes this knowledge can lead to a
     /// more accurate cost estimation.
-    bool isHighCostExpansion(const SCEV *Expr, Loop *L,
+    bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget,
                              const TargetTransformInfo *TTI,
                              const Instruction *At = nullptr) {
       SmallPtrSet<const SCEV *, 8> Processed;
-      return isHighCostExpansionHelper(Expr, L, At, TTI, Processed);
+      int BudgetRemaining = Budget * TargetTransformInfo::TCC_Basic;
+      return isHighCostExpansionHelper(Expr, L, At, BudgetRemaining, TTI,
+                                       Processed);
     }
 
     /// This method returns the canonical induction variable of the specified
     /// type for the specified loop (inserting one if there is none).  A
     /// canonical induction variable starts at zero and steps by one on each
     /// iteration.
     PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty);
 
#endif
     Optional<ScalarEvolution::ValueOffsetPair>
     getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
 
   private:
     LLVMContext &getContext() const { return SE.getContext(); }
 
     /// Recursive helper function for isHighCostExpansion.
     bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
-                                   const Instruction *At,
+                                   const Instruction *At, int &BudgetRemaining,
                                    const TargetTransformInfo *TTI,
                                    SmallPtrSetImpl<const SCEV *> &Processed);
 
     /// Insert the specified binary operator, doing a small amount of work to
     /// avoid inserting an obviously redundant operation, and hoisting to an
     /// outer loop when the opportunity is there and it is safe.
     Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
                        SCEV::NoWrapFlags Flags, bool IsSafeToHoist);

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
+
+cl::opt<unsigned> llvm::SCEVCheapExpansionBudget(
+    "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),
+    cl::desc("When performing SCEV expansion only if it is cheap to do, this "
+             "controls the budget that is considered cheap (default = 4)"));
+
 using namespace PatternMatch;
 
 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
 /// reusing an existing cast if a suitable one exists, moving an existing
 /// cast if a suitable one exists but isn't in the right place, or
 /// creating a new one.
 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
                                        Instruction::CastOps Op,
SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
   // There is potential to make this significantly smarter, but this simple
   // heuristic already gets some interesting cases.
 
   // Can not find suitable value.
   return None;
 }
 
 bool SCEVExpander::isHighCostExpansionHelper(
-    const SCEV *S, Loop *L, const Instruction *At,
+    const SCEV *S, Loop *L, const Instruction *At, int &BudgetRemaining,
     const TargetTransformInfo *TTI, SmallPtrSetImpl<const SCEV *> &Processed) {
   // If we can find an existing value for this scev available at the point "At"
   // then consider the expression cheap.
   if (At && getRelatedExistingExpansion(S, At, L))
     return false;
 
   // Zero/One operand expressions
   switch (S->getSCEVType()) {
   case scUnknown:
   case scConstant:
     return false;
   case scTruncate:
     return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(), L,
-                                     At, TTI, Processed);
+                                     At, BudgetRemaining, TTI, Processed);
   case scZeroExtend:
     return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(),
-                                     L, At, TTI, Processed);
+                                     L, At, BudgetRemaining, TTI, Processed);
   case scSignExtend:
     return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
-                                     L, At, TTI, Processed);
+                                     L, At, BudgetRemaining, TTI, Processed);
   }
 
   if (!Processed.insert(S).second)
     return false;
 
   if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     // If the divisor is a power of two and the SCEV type fits in a native
     // integer (and the LHS not expensive), consider the division cheap
     // irrespective of whether it occurs in the user code since it can be
     // lowered into a right shift.
     if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
       if (SC->getAPInt().isPowerOf2()) {
-        if (isHighCostExpansionHelper(UDivExpr->getLHS(), L, At, TTI,
-                                      Processed))
+        if (isHighCostExpansionHelper(UDivExpr->getLHS(), L, At,
+                                      BudgetRemaining, TTI, Processed))
           return true;
         const DataLayout &DL =
             L->getHeader()->getParent()->getParent()->getDataLayout();
         unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
         return DL.isIllegalInteger(Width);
       }
 
     // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
bool SCEVExpander::isHighCostExpansionHelper(
   if (isa<SCEVMinMaxExpr>(S))
     return true;
 
   // Recurse past nary expressions, which commonly occur in the
   // BackedgeTakenCount. They may already exist in program code, and if not,
   // they are not too expensive rematerialize.
   if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) {
     for (auto *Op : NAry->operands())
-      if (isHighCostExpansionHelper(Op, L, At, TTI, Processed))
+      if (isHighCostExpansionHelper(Op, L, At, BudgetRemaining, TTI, Processed))
         return true;
   }
 
   // If we haven't recognized an expensive SCEV pattern, assume it's an
   // expression produced by program code.
   return false;
 }
 

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

for (BasicBlock *ExitingBB : ExitingBlocks) {
         continue;
 
       PHINode *IndVar = FindLoopCounter(L, ExitingBB, ExitCount, SE, DT);
       if (!IndVar)
         continue;
 
       // Avoid high cost expansions.  Note: This heuristic is questionable in
       // that our definition of "high cost" is not exactly principled.
-      if (Rewriter.isHighCostExpansion(ExitCount, L, TTI))
+      if (Rewriter.isHighCostExpansion(ExitCount, L, SCEVCheapExpansionBudget,
+                                       TTI))
         continue;
 
       // Check preconditions for proper SCEVExpander operation. SCEV does not
       // express SCEVExpander's dependencies, such as LoopSimplify. Instead
       // any pass that uses the SCEVExpander must do it. This does not work
       // well for loop passes because SCEVExpander makes assumptions about
       // all loops, while LoopPassManager only forces the current loop to be
       // simplified.

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

if (isa<SCEVCouldNotCompute>(TripCountSC)) {
     return false;
   }
 
   BasicBlock *PreHeader = L->getLoopPreheader();
   BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
   const DataLayout &DL = Header->getModule()->getDataLayout();
   SCEVExpander Expander(*SE, DL, "loop-unroll");
   if (!AllowExpensiveTripCount &&
-      Expander.isHighCostExpansion(TripCountSC, L, TTI, PreHeaderBR)) {
+      Expander.isHighCostExpansion(TripCountSC, L, SCEVCheapExpansionBudget,
+                                   TTI, PreHeaderBR)) {
     LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
     return false;
   }
 
   // This constraint lets us deal with an overflowing trip count easily; see the
   // comment on ModVal below.
   if (Log2_32(Count) > BEWidth) {
     LLVM_DEBUG(

llvm/lib/Transforms/Utils/LoopUtils.cpp

while ((PN = dyn_cast<PHINode>(BBI++))) {
         // away. Avoid doing so unless we know we have a value which computes
         // the ExitValue already. TODO: This should be merged into SCEV
         // expander to leverage its knowledge of existing expressions.
         if (ReplaceExitValue != AlwaysRepl &&
             !isa<SCEVConstant>(ExitValue) && !isa<SCEVUnknown>(ExitValue) &&
             hasHardUserWithinLoop(L, Inst))
           continue;
 
-        bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, TTI, Inst);
+        bool HighCost = Rewriter.isHighCostExpansion(
+            ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
         Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
 
         LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = "
                           << *ExitVal << '\n' << "  LoopVal = " << *Inst
                           << "\n");
 
         if (!isValidRewrite(SE, Inst, ExitVal)) {
           DeadInsts.push_back(ExitVal);

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
 
   // Get the symbolic expression for this instruction.
   const SCEV *S = SE->getSCEV(I);
 
   if (!SE->isLoopInvariant(S, L))
     return false;
 
   // Do not generate something ridiculous even if S is loop invariant.
-  if (Rewriter.isHighCostExpansion(S, L, TTI, I))
+  if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))
     return false;
 
   auto *IP = GetLoopInvariantInsertPosition(L, I);
   auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
 
   I->replaceAllUsesWith(Invariant);
   LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
                     << " with loop invariant: " << *S << '\n');