[SCEV] Look through zero-extends in howFarToZero

[kparzysz]

Summary

An expression like (zext i2 {(trunc i32 (1 + %B) to i2),+,1}<%while.body> to i32) will become zero exactly when the nested value becomes zero in its type. Instead of converting this kind of a zero-extended value into an addrec with predicates, simply remove the zext.

This is the replacement of D47899 (the motivation is explained there).

[kparzysz]

lib/Analysis/ScalarEvolution.cpp

8268 ↗

(On Diff #150532)

Accidental deletion.

[efriedma]

Makes sense. Probably should also handle SCEVSignExtendExpr.

(Needs testcases.)

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

8281 ↗

(On Diff #150532)

Probably better to do V = StripInjectiveFunctions(V) where StripInjectiveFunctions strips sign and zero extends before we check if V is an add rec or not.

[kparzysz]

Implemented stripInjectiveFunctions (that strips sign- and zero-extensions) and used it in howFarToZero. Added a testcase.

[sanjoy]

lgtm

lib/Analysis/ScalarEvolution.cpp

8153 ↗

(On Diff #150557)

General convention is to use S for SCEV* variables, not Val.

test/Analysis/ScalarEvolution/strip-injective-zext.ll

18 ↗

(On Diff #150557)

Minor: the test can probably be simplified a little bit more:

• Use an i64 pointer instead of the %s.0 pointer
• Strip unnecessary function attributes like dso_local, local_unnamed_addr, TBAA etc.

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

private:
   /// Get add expr already created or create a new one.
   const SCEV *getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                                  SCEV::NoWrapFlags Flags);
 
   /// Get mul expr already created or create a new one.
   const SCEV *getOrCreateMulExpr(SmallVectorImpl<const SCEV *> &Ops,
                                  SCEV::NoWrapFlags Flags);
 
+  /// Return x if \p Val is f(x) where f is a 1-1 function.
+  const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
+
   /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
   /// A loop is considered "used" by an expression if it contains
   /// an add rec on said loop.
   void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
 
   /// Find all of the loops transitively used in \p S, and update \c LoopUsers
   /// accordingly.
   void addToLoopUseLists(const SCEV *S);

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
 
   llvm_unreachable("Unknown SCEV type!");
 }
 
 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
   return getSCEVAtScope(getSCEV(V), L);
 }
 
+const SCEV *ScalarEvolution::stripInjectiveFunctions(const SCEV *S) const {
+  if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S))
+    return stripInjectiveFunctions(ZExt->getOperand());
+  if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S))
+    return stripInjectiveFunctions(SExt->getOperand());
+  return S;
+}
+
 /// Finds the minimum unsigned root of the following equation:
 ///
 ///     A * X = B (mod N)
 ///
 /// where N = 2^BW and BW is the common bit width of A and B. The signedness of
 /// A and B isn't important.
 ///
 /// If the equation does not have a solution, SCEVCouldNotCompute is returned.
ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit,
   SmallPtrSet<const SCEVPredicate *, 4> Predicates;
   // If the value is a constant
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
     // If the value is already zero, the branch will execute zero times.
     if (C->getValue()->isZero()) return C;
     return getCouldNotCompute();  // Otherwise it will loop infinitely.
   }
 
-  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
+  const SCEVAddRecExpr *AddRec =
+      dyn_cast<SCEVAddRecExpr>(stripInjectiveFunctions(V));
+
   if (!AddRec && AllowPredicates)
     // Try to make this an AddRec using runtime tests, in the first X
     // iterations of this loop, where X is the SCEV expression found by the
     // algorithm below.
     AddRec = convertSCEVToAddRecWithPredicates(V, L, Predicates);
 
   if (!AddRec || AddRec->getLoop() != L)
     return getCouldNotCompute();

llvm/trunk/test/Analysis/ScalarEvolution/strip-injective-zext.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+; The initial SCEV for the backedge count is
+;   (zext i2 {(trunc i32 (1 + %a1) to i2),+,1}<%b2> to i32).
+; In howFarToZero, this was further converted to an add-rec, the complexity
+; of which defeated the calculation of the backedge taken count.
+; Since such zero-extensions preserve the values being extended, strip
+; them in howFarToZero to simplify the input SCEV.
+
+; Check that the backedge taken count was actually computed:
+; CHECK: Determining loop execution counts for: @f0
+; CHECK-NEXT: Loop %b2: backedge-taken count is (-1 * (trunc i32 (1 + %a1) to i2))
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
+
+define i32 @f0(i32 %a0, i32 %a1, i32* nocapture %a2) #0 {
+b0:
+  %v0 = and i32 %a1, 3
+  %v1 = icmp eq i32 %v0, 0
+  br i1 %v1, label %b4, label %b1
+
+b1:                                               ; preds = %b0
+  %v2 = shl i32 %a0, 7
+  %v3 = add i32 %v2, -128
+  br label %b2
+
+b2:                                               ; preds = %b2, %b1
+  %v4 = phi i32 [ %a1, %b1 ], [ %v9, %b2 ]
+  %v5 = phi i32* [ %a2, %b1 ], [ %v8, %b2 ]
+  %v6 = getelementptr inbounds i32, i32* %v5, i32 0
+  store i32 %v3, i32* %v6, align 4
+  %v8 = getelementptr inbounds i32, i32* %v5, i32 1
+  %v9 = add nsw i32 %v4, 1
+  %v10 = and i32 %v9, 3
+  %v11 = icmp eq i32 %v10, 0
+  br i1 %v11, label %b3, label %b2
+
+b3:                                               ; preds = %b2
+  br label %b4
+
+b4:                                               ; preds = %b3, %b0
+  ret i32 0
+}
+
+attributes #0 = { norecurse nounwind }