[SCEV] Support mul in SCEVLoopGuardRewriter

[dmakogon]

Summary

Adds support for these SCEVs to cover more cases.

[dmakogon]

Fixes regression introduced by https://reviews.llvm.org/D145230

[nikic]

We could also rewrite all types like this: https://github.com/llvm/llvm-project/commit/137e813953991caa93cfe439808618045a3e6311

There is a bit of compile time impact from doing that (though in part it's code size correlated): http://llvm-compile-time-tracker.com/compare.php?from=e00c73c856a325008afead10cfb3e9d0fc4a1e41&to=137e813953991caa93cfe439808618045a3e6311&stat=instructions:u
And code size seems to consistently increase: http://llvm-compile-time-tracker.com/compare.php?from=e00c73c856a325008afead10cfb3e9d0fc4a1e41&to=137e813953991caa93cfe439808618045a3e6311&stat=size-text Not sure if that means something is going wrong, or all optimizations this enables happen to be size increasing.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/trip-count-minmax.ll

168

Regression

llvm/test/Analysis/ScalarEvolution/trip-count9.ll

286

Regression. Do you know why?

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/trip-count9.ll

424

Same

[mkazantsev]

I do not know if this trip count is used for anything useful, but its fragility is concerning.

llvm/lib/Analysis/ScalarEvolution.cpp

public:
   }
 
   const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
     auto I = Map.find(Expr);
     if (I == Map.end())
       return SCEVRewriteVisitor<SCEVLoopGuardRewriter>::visitSMinExpr(Expr);
     return I->second;
   }
+  
+  const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
+    auto I = Map.find(Expr);
+    if (I == Map.end())
+      return SCEVRewriteVisitor<SCEVLoopGuardRewriter>::visitMulExpr(Expr);
+    return I->second;
+  }
 };
 
 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) {
   SmallVector<const SCEV *> ExprsToRewrite;
   auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,
                               const SCEV *RHS,
                               DenseMap<const SCEV *, const SCEV *>
                                   &RewriteMap) {

llvm/test/Analysis/ScalarEvolution/trip-count-minmax.ll

 ; CHECK-NEXT:  Classifying expressions for: @smin
 ; CHECK-NEXT:    %mul = shl nsw i32 %a, 1
 ; CHECK-NEXT:    --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647)
 ; CHECK-NEXT:    %mul1 = shl nsw i32 %b, 2
 ; CHECK-NEXT:    --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645)
 ; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
 ; CHECK-NEXT:    --> ((2 * %a)<nsw> smin (4 * %b)<nsw>) U: [0,-1) S: [-2147483648,2147483645)
 ; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
-; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>)) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>)) LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a)<nsw> smin (4 * %b)<nsw>) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: ((2 * %a)<nsw> smin (4 * %b)<nsw>) LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @smin
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
-; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -3
+; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483646
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %for.body: Trip multiple is 2
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 ; void smin(signed a, signed b) {
 ;   a *= 2;
 ;   b *= 4;
 ;   int N = a < b ? a : b;
 ;   for (int i = 0; i < N; ++i) {
 ;     foo();
 ;   }

llvm/test/Analysis/ScalarEvolution/trip-count9.ll

 define void @even(i4 %n) {
 ; CHECK-LABEL: 'even'
 ; CHECK-NEXT:  Determining loop execution counts for: @even
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (2 * %n))
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 5
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (2 * %n))
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + (2 * %n))
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %loop: Trip multiple is 2
+; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %m = shl i4 %n, 1
   %s = icmp sgt i4 %m, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
   %i.next = add i4 %i, 1

 define void @even_nsw(i4 %n) {
 ; CHECK-LABEL: 'even_nsw'
 ; CHECK-NEXT:  Determining loop execution counts for: @even_nsw
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (2 * %n))
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 5
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (2 * %n))
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + (2 * %n))
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %loop: Trip multiple is 2
+; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %m = shl i4 %n, 1
   %s = icmp sgt i4 %m, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 1