[SCEV] Smart range calculation for SCEVUnknown Phis

[mkazantsev]

Summary

The range of SCEVUnknown Phi which merges values X1, X2, ..., XN
can be evaluated as U(Range(X1), Range(X2), ..., Range(XN)).

[mkazantsev]

Added a test with cycled phis to show explicitly that we do not crush on them.

[sanjoy]

lgtm

include/llvm/Analysis/ScalarEvolution.h

1102

Triple slash to be consistent.

1103

Might want to make this a set of PHINode to make what we store here obvious in the type system.

lib/Analysis/ScalarEvolution.cpp

5537

Can this be a range for?

5545

assert that deletion was successful.

include/llvm/Analysis/ScalarEvolution.h

using ValueExprMapType =
       DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>;
 
   /// This is a cache of the values we have analyzed so far.
   ValueExprMapType ValueExprMap;
 
   /// Mark predicate values currently being processed by isImpliedCond.
   SmallPtrSet<Value *, 6> PendingLoopPredicates;
 
+  // Mark SCEVUnknown Phis currently being processed by getRangeRef.
+  SmallPtrSet<const SCEVUnknown *, 6> PendingPhiRanges;
+
   /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
   /// conditions dominating the backedge of a loop.
   bool WalkingBEDominatingConds = false;
 
   /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
   /// predicate by splitting it into a set of independent predicates.
   bool ProvingSplitPredicate = false;
 

lib/Analysis/ScalarEvolution.cpp

if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
              "generalize as needed!");
       unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, &AC, nullptr, &DT);
       if (NS > 1)
         ConservativeResult = ConservativeResult.intersectWith(
             ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
                           APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1));
     }
 
+    // A range of Phi is a subset of union of all ranges of its input.
+    if (const PHINode *Phi = dyn_cast<PHINode>(U->getValue())) {
+      // Make sure that we do not run over cycled Phis.
+      if (PendingPhiRanges.insert(U).second) {
+        ConstantRange RangeFromOps(BitWidth, /*isFullSet=*/false);
+        for (int i = 0, e = Phi->getNumOperands(); i < e; ++i) {
+          auto OpRange = getRangeRef(getSCEV(Phi->getOperand(i)), SignHint);
+          RangeFromOps = RangeFromOps.unionWith(OpRange);
+          // No point to continue if we already have a full set.
+          if (RangeFromOps.isFullSet())
+            break;
+        }
+        ConservativeResult = ConservativeResult.intersectWith(RangeFromOps);
+        PendingPhiRanges.erase(U);
+      }
+    }
+
     return setRange(U, SignHint, std::move(ConservativeResult));
   }
 
   return setRange(S, SignHint, std::move(ConservativeResult));
 }
 
 // Given a StartRange, Step and MaxBECount for an expression compute a range of
 // values that the expression can take. Initially, the expression has a value
ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI,
   HasGuards = GuardDecl && !GuardDecl->use_empty();
 }
 
 ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
     : F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
       LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)),
       ValueExprMap(std::move(Arg.ValueExprMap)),
       PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
+      PendingPhiRanges(std::move(Arg.PendingPhiRanges)),
       MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),
       ConstantEvolutionLoopExitValue(
           std::move(Arg.ConstantEvolutionLoopExitValue)),
       ValuesAtScopes(std::move(Arg.ValuesAtScopes)),
       LoopDispositions(std::move(Arg.LoopDispositions)),
ScalarEvolution::~ScalarEvolution() {
   // Free any extra memory created for ExitNotTakenInfo in the unlikely event
   // that a loop had multiple computable exits.
   for (auto &BTCI : BackedgeTakenCounts)
     BTCI.second.clear();
   for (auto &BTCI : PredicatedBackedgeTakenCounts)
     BTCI.second.clear();
 
   assert(PendingLoopPredicates.empty() && "isImpliedCond garbage");
+  assert(PendingPhiRanges.empty() && "getRangeRef garbage");
   assert(!WalkingBEDominatingConds && "isLoopBackedgeGuardedByCond garbage!");
   assert(!ProvingSplitPredicate && "ProvingSplitPredicate garbage!");
 }
 
 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
   return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
 }
 

test/Analysis/ScalarEvolution/unknown_phis.ll

+; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
+
+define void @merge_values_with_ranges(i32 *%a_len_ptr, i32 *%b_len_ptr, i1 %unknown_cond) {
+
+; CHECK-LABEL: Classifying expressions for: @merge_values_with_ranges
+; CHECK:       %len = phi i32 [ %len_a, %if.true ], [ %len_b, %if.false ]
+; CHECK-NEXT:  -->  %len U: [0,2147483647) S: [0,2147483647)
+
+ entry:
+  br i1 %unknown_cond, label %if.true, label %if.false
+
+if.true:
+  %len_a = load i32, i32* %a_len_ptr, !range !0
+  br label %merge
+
+if.false:
+  %len_b = load i32, i32* %b_len_ptr, !range !0
+  br label %merge
+
+merge:
+  %len = phi i32 [ %len_a, %if.true ], [ %len_b, %if.false ]
+  ret void
+}
+
+define void @merge_values_with_ranges_looped(i32 *%a_len_ptr, i32 *%b_len_ptr) {
+
+; TODO: We could be much smarter here. So far we just make sure that we do not
+;       go into infinite loop analyzing these Phis.
+
+; CHECK-LABEL: Classifying expressions for: @merge_values_with_ranges_looped
+; CHECK:       %p1 = phi i32 [ %len_a, %entry ], [ %p2, %loop ]
+; CHECK-NEXT:  -->  %p1 U: full-set S: full-set
+; CHECK:         %p2 = phi i32 [ %len_b, %entry ], [ %p1, %loop ]
+; CHECK-NEXT:  -->  %p2 U: full-set S: full-set
+
+ entry:
+  %len_a = load i32, i32* %a_len_ptr, !range !0
+  %len_b = load i32, i32* %b_len_ptr, !range !0
+  br label %loop
+
+loop:
+  %p1 = phi i32 [ %len_a, %entry ], [ %p2, %loop ]
+  %p2 = phi i32 [ %len_b, %entry ], [ %p1, %loop ]
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i32 %iv, 1
+  %loop.cond = icmp slt i32 %iv.next, 100
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+
+!0 = !{i32 0, i32 2147483647}

test/Transforms/IRCE/single-access-no-preloop.ll

  exit:
   ret void
 }
 
 ; CHECK-LABEL: @single_access_empty_range_2(
 ; CHECK-NOT:   br i1 false
 ; CHECK-NOT:   preloop
 
+define void @single_access_no_preloop_no_offset_phi_len(i32 *%arr, i32 *%a_len_ptr, i32 *%b_len_ptr, i32 %n, i1 %unknown_cond) {
+ entry:
+  br i1 %unknown_cond, label %if.true, label %if.false
+
+if.true:
+  %len_a = load i32, i32* %a_len_ptr, !range !0
+  br label %merge
+
+if.false:
+  %len_b = load i32, i32* %b_len_ptr, !range !0
+  br label %merge
+
+merge:
+  %len = phi i32 [ %len_a, %if.true ], [ %len_b, %if.false ]
+  %first.itr.check = icmp sgt i32 %n, 0
+  br i1 %first.itr.check, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %merge ] , [ %idx.next, %in.bounds ]
+  %idx.next = add i32 %idx, 1
+  %abc = icmp slt i32 %idx, %len
+  br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
+
+ in.bounds:
+  %addr = getelementptr i32, i32* %arr, i32 %idx
+  store i32 0, i32* %addr
+  %next = icmp slt i32 %idx.next, %n
+  br i1 %next, label %loop, label %exit
+
+ out.of.bounds:
+  ret void
+
+ exit:
+  ret void
+}
+
+; CHECK-LABEL: @single_access_no_preloop_no_offset_phi_len(
+
+; CHECK: loop:
+; CHECK: br i1 true, label %in.bounds, label %out.of.bounds
+
+; CHECK: main.exit.selector:
+; CHECK-NEXT: %idx.next.lcssa = phi i32 [ %idx.next, %in.bounds ]
+; CHECK-NEXT: [[continue:%[^ ]+]] = icmp slt i32 %idx.next.lcssa, %n
+; CHECK-NEXT: br i1 [[continue]], label %main.pseudo.exit, label %exit.loopexit
+
+; CHECK: main.pseudo.exit:
+; CHECK-NEXT: %idx.copy = phi i32 [ 0, %loop.preheader ], [ %idx.next.lcssa, %main.exit.selector ]
+; CHECK-NEXT: %indvar.end = phi i32 [ 0, %loop.preheader ], [ %idx.next.lcssa, %main.exit.selector ]
+; CHECK-NEXT: br label %postloop
+
+; CHECK: postloop:
+; CHECK-NEXT: br label %loop.postloop
+
+; CHECK: loop.postloop:
+; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.next.postloop, %in.bounds.postloop ], [ %idx.copy, %postloop ]
+; CHECK-NEXT: %idx.next.postloop = add i32 %idx.postloop, 1
+; CHECK-NEXT: %abc.postloop = icmp slt i32 %idx.postloop, %len
+; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds
+
+; CHECK: in.bounds.postloop:
+; CHECK-NEXT: %addr.postloop = getelementptr i32, i32* %arr, i32 %idx.postloop
+; CHECK-NEXT: store i32 0, i32* %addr.postloop
+; CHECK-NEXT: %next.postloop = icmp slt i32 %idx.next.postloop, %n
+; CHECK-NEXT: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit
+
 !0 = !{i32 0, i32 2147483647}
 !1 = !{!"branch_weights", i32 64, i32 4}

test/Transforms/LoopVectorize/X86/consecutive-ptr-cg-bug.ll

 ; in-place IV optimization by replacing:
 ;   %8 = phi i32 [ %.ph2, %.outer ], [ %7, %6 ] with
 ; with
 ;   %8 = sub i32 %7, 1.
 
 
 ; Verify that store is vectorized as stride-1 memory access.
 
-; CHECK: vector.body:
-; CHECK: store <4 x i32>
+; CHECK-LABEL: @test_01(
+; CHECK-NOT: vector.body:
 
+; This test was originally vectorized, but now SCEV is smart enough to prove
+; that its trip count is 1, so it gets ignored by vectorizer.
 ; Function Attrs: uwtable
-define void @test() {
+define void @test_01() {
   br label %.outer
 
 ; <label>:1:                                      ; preds = %2
   ret void
 
 ; <label>:2:                                      ; preds = %._crit_edge.loopexit
   %3 = add nsw i32 %.ph, -2
   br i1 undef, label %1, label %.outer
; <label>:6:                                      ; preds = %6, %.outer
   %13 = add i32 %7, 1
   %14 = icmp sgt i32 %13, 61
   br i1 %14, label %._crit_edge.loopexit, label %6
 
 ._crit_edge.loopexit:                             ; preds = %._crit_edge.loopexit, %6
   br i1 undef, label %2, label %._crit_edge.loopexit
 }
 
+; After trip count is increased, the test gets vectorized.
+; CHECK-LABEL: @test_02(
+; CHECK: vector.body:
+; CHECK: store <4 x i32>
+
+; Function Attrs: uwtable
+define void @test_02() {
+  br label %.outer
+
+; <label>:1:                                      ; preds = %2
+  ret void
+
+; <label>:2:                                      ; preds = %._crit_edge.loopexit
+  %3 = add nsw i32 %.ph, -2
+  br i1 undef, label %1, label %.outer
+
+.outer:                                           ; preds = %2, %0
+  %.ph = phi i32 [ %3, %2 ], [ 336, %0 ]
+  %.ph2 = phi i32 [ 62, %2 ], [ 110, %0 ]
+  %4 = and i32 %.ph, 30
+  %5 = add i32 %.ph2, 1
+  br label %6
+
+; <label>:6:                                      ; preds = %6, %.outer
+  %7 = phi i32 [ %5, %.outer ], [ %13, %6 ]
+  %8 = phi i32 [ %.ph2, %.outer ], [ %7, %6 ]
+  %9 = add i32 %8, 2
+  %10 = zext i32 %9 to i64
+  %11 = getelementptr inbounds i32, i32 addrspace(1)* undef, i64 %10
+  %12 = ashr i32 undef, %4
+  store i32 %12, i32 addrspace(1)* %11, align 4
+  %13 = add i32 %7, 1
+  %14 = icmp sgt i32 %13, 610
+  br i1 %14, label %._crit_edge.loopexit, label %6
+
+._crit_edge.loopexit:                             ; preds = %._crit_edge.loopexit, %6
+  br i1 undef, label %2, label %._crit_edge.loopexit
+}