[SCEV] Attempt to define what flags are legal on a SCEV

[reames]

Summary

This is an attempt to define what the current semantics are closest too. The existence of D106852 does imply these semantics are not 100% correct, but that piece of code is one of handful of places which are known to violate them. https://bugs.llvm.org/show_bug.cgi?id=51817 tracks the list of currently known violations of the proposed rules so that they don't get forgotten.

This is inspired by the discussion on D106852. If we accept these semantics, then the resolution to D106852 becomes obvious, if painful.

[efriedma]

Description makes sense to me.

llvm/include/llvm/Analysis/ScalarEvolution.h

123

I think we assert that the operands of an AddRec are loop-invariant, so the extra text isn't relevant.

132

Existence.

[reames]

Simplify per Eli's observation

[reames]

And the typo fix missed the first time

llvm/include/llvm/Analysis/ScalarEvolution.h

123

I'd thought we'd allowed this, but a quick test seems to say no, so removed.

[mkazantsev]

I think it's too pessmistic with regard of users. Imagine the following situation: we have %a and %b which are SCEVUnknown, and the only their (SCEV) user is a + b which is guarded by conditions a <u 100, b <u 100.

We might have a right to say that a + b is nuw and nsw, since the only place where it is used is guarded by conditions that imply this. But in the suggested definition, basically, guarding conditions don't matter and we cannot infer any flags from them. It means that we can still prove some facts, but it will take us walking dom tree every time we need it.

On the other hand, I understand the motivation, and implications of alternative (use-based) approach for SCEV expander. So what I said is just a highlight of a problem we are going to inherit, not a con against this patch.

If everyone's agree then it's fine for me.

llvm/include/llvm/Analysis/ScalarEvolution.h

118

described?

[reames]

I think @mkazantsev has pointed out something a bit nasty. The current applyLoopGuard code does use contextual knowledge to build new SCEVs, and does appear to violate the proposed rules here. (e.g. it produces a new SCEV with flags specific to the context without consideration of the defining scope.) Skimming the code, I only see one use that appears invalid by the new rules (the urem matching).

I think our best option is to proceed with this definition and consider that one cases as bug. We need to get to something consistent before we can start moving towards a better design.

edit: Treating this as a bug appears to be low impact. A local change which uses conservative flags for the multiply in the urem case causes zero test diffs.

[reames]

Fix the violation of proposed rules noticed in applyLoopGuards. No test impact.

[reames]

I seem to like to forget typo fixes when reving patches...

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

13512

I think the expression here is naturally nuw: (X /u Y) * Y must be less than or equal to X. No idea why it's getting marked nsw, though.

Anyway, we can deal with various violations (e.g. ScalarEvolution::getGEPExpr) in future patches.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

13512

I agree on the definitional nature of the nuw. I'll simplify point out that because it is definitional, it should be in getMulExpr, not here. Interestingly, it's not.

I'd still argue for removing here since it appears to have no test coverage.

I hadn't noticed the issue in getGEPExpr previously, that one is nasty. I'm going to go ahead and file a bug to keep track of the issues as we find them.

[reames]

Remove the applyLoopGuard fix as the preference seems to be to handle that in a separate change.

[reames]

Reviewers, are we comfortable with this path forward? If so, I'd like to go ahead and land this so that I can start working on the fixes for the known violations (noted in the bug linked in the review comment).

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// its start value if the step is non-zero.  Computing the same value on
   /// each iteration is not considered wrapping, and recurrences with step = 0
   /// are trivially <NW>.  <NW> is independent of the sign of step and the
   /// value the add recurrence starts with.
   ///
   /// Note that NUW and NSW are also valid properties of a recurrence, and
   /// either implies NW. For convenience, NW will be set for a recurrence
   /// whenever either NUW or NSW are set.
+  ///
+  /// We require that the flag on a SCEV apply to the entire scope in which
+  /// that SCEV is defined.  A SCEV's scope is set of locations dominated by
+  /// a defining location, which is in turn describes by the following rules:
+  /// * A SCEVUnknown is at the point of definition of the Value.
+  /// * A SCEVConstant is defined at all points.
+  /// * A SCEVAddRec is defined starting with the header of the associated
+  ///   loop.
+  /// * All other SCEVs are defined at the earlest point all operands are
+  ///   defined.
+  ///
+  /// The above rules describe a maximally hoisted form (without regards to
+  /// potential control dependence).  A SCEV is defined anywhere a
+  /// corresponding instruction could be defined in said maximally hoisted
+  /// form.  Note that SCEVUDivExpr (currently the only expression type which
+  /// can trap) can be defined per these rules in regions where it would trap
+  /// at runtime.  A SCEV being defined does not require the existence of any
+  /// instruction within the defined scope.
   enum NoWrapFlags {
     FlagAnyWrap = 0,    // No guarantee.
     FlagNW = (1 << 0),  // No self-wrap.
     FlagNUW = (1 << 1), // No unsigned wrap.
     FlagNSW = (1 << 2), // No signed wrap.
     NoWrapMask = (1 << 3) - 1
   };
 

llvm/lib/Analysis/ScalarEvolution.cpp

if (I == Map.end())
       return Expr;
     return I->second;
   }
 };
 
 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) {
   auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,
                               const SCEV *RHS, ValueToSCEVMapTy &RewriteMap) {
+    // WARNING: It is generally unsound to apply any wrap flags to the proposed
+    // replacement SCEV which isn't directly implied by the replacee SCEV.  In
+    // particular, using contextual facts to imply flags is *NOT* legal.  See
+    // the scoping rules for flags in the header to understand why.
+
     // If we have LHS == 0, check if LHS is computing a property of some unknown
     // SCEV %v which we can rewrite %v to express explicitly.
     const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS);
     if (Predicate == CmpInst::ICMP_EQ && RHSC &&
         RHSC->getValue()->isNullValue()) {
       // If LHS is A % B, i.e. A % B == 0, rewrite A to (A /u B) * B to
       // explicitly express that.
       const SCEV *URemLHS = nullptr;
       const SCEV *URemRHS = nullptr;
       if (matchURem(LHS, URemLHS, URemRHS)) {
         if (const SCEVUnknown *LHSUnknown = dyn_cast<SCEVUnknown>(URemLHS)) {
           Value *V = LHSUnknown->getValue();
           auto Multiple =
               getMulExpr(getUDivExpr(URemLHS, URemRHS), URemRHS,
-                         (SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNSW));
+                         SCEV::FlagAnyWrap);
           RewriteMap[V] = Multiple;
           return;
         }
       }
     }
 
     if (!isa<SCEVUnknown>(LHS) && isa<SCEVUnknown>(RHS)) {
       std::swap(LHS, RHS);