[SCEV] Compute AddRec range computations using different type BECount

[caojoshua]

Summary

Before this patch, we can only use the MaxBECount for an AddRec's range
computation if the MaxBECount has <= bit width of the AddRec. This patch
reasons that if a MaxBECount has > bit width, and is <= the max value of
AddRec's bit width, we can still use the MaxBECount.

[caojoshua]

Clean up code a bit

[caojoshua]

I've no idea if the Dependence Analysis test change is correct. Would appreciate if reviews can look at it.

[nikic]

Nice find! It looks like there are some polly tests that need updating.

llvm/lib/Analysis/ScalarEvolution.cpp

6710

static_cast -> cast

6712

.getActiveBits() <= BitWidth?

6723

It would probably make sense to convert this MaxBECount argument into an APInt (maybe as an NFC-refactoring before this change)?

[caojoshua]

• Rebase on top of a refactoring patch
• Update polly tests. One test looks functionally the same, and the other test finds tighter bounds. Looks ok to me.

[nikic]

LGTM

polly/test/CodeGen/switch-in-non-affine-region.ll

17–23

Don't match ; preds

[uabelho]

Hi,

The following starts failing with this patch:

opt -verify-scev -passes="loop(loop-unroll-full),loop-mssa(licm<allowspeculation>,indvars,loop-rotate)" bbi-83618.ll -o /dev/null

We get

Incorrect cached computation in ConstantMultipleCache for (-1 * (zext i16 {0,+,6}<nuw><%for.body> to i64))<nuw><nsw> : Computed -6 but cache contains -2!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: ../../main-github/llvm/build-all/bin/opt -verify-scev -passes=loop(loop-unroll-full),loop-mssa(licm<allowspeculation>,indvars,loop-rotate) bbi-83618.ll -o /dev/null
 #0 0x00005647691c5b77 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../main-github/llvm/build-all/bin/opt+0x2db3b77)
 #1 0x00005647691c389e llvm::sys::RunSignalHandlers() (../../main-github/llvm/build-all/bin/opt+0x2db189e)
 #2 0x00005647691c620f SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f850faf2630 __restore_rt sigaction.c:0:0
 #4 0x00007f850d239387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007f850d23aa78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00005647683ab616 llvm::ScalarEvolution::verify() const (../../main-github/llvm/build-all/bin/opt+0x1f99616)
 #7 0x0000564769cf7f36 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x38e5f36)
 #8 0x00005647693e0b5d llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x2fceb5d)
 #9 0x0000564768bd4ff4 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x27c2ff4)
#10 0x0000564767089c4d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0xc77c4d)
#11 0x0000564768bd93de llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x27c73de)
#12 0x00005647670899ed llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0xc779ed)
#13 0x0000564768bd4184 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x27c2184)
#14 0x0000564766cc4a1e llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (../../main-github/llvm/build-all/bin/opt+0x8b2a1e)
#15 0x0000564766cd30ee main (../../main-github/llvm/build-all/bin/opt+0x8c10ee)
#16 0x00007f850d225555 __libc_start_main (/lib64/libc.so.6+0x22555)
#17 0x0000564766cbf170 _start (../../main-github/llvm/build-all/bin/opt+0x8ad170)
Abort (core dumped)

bbi-83618.ll1 KBDownload

[uabelho]

In D151698#4420612, @uabelho wrote:

Hi,

The following starts failing with this patch:

opt -verify-scev -passes="loop(loop-unroll-full),loop-mssa(licm<allowspeculation>,indvars,loop-rotate)" bbi-83618.ll -o /dev/null

I wrote https://github.com/llvm/llvm-project/issues/63385 about it.

[uabelho]

In D151698#4432010, @uabelho wrote:

In D151698#4420612, @uabelho wrote:

Hi,

The following starts failing with this patch:

opt -verify-scev -passes="loop(loop-unroll-full),loop-mssa(licm<allowspeculation>,indvars,loop-rotate)" bbi-83618.ll -o /dev/null

I wrote https://github.com/llvm/llvm-project/issues/63385 about it.

Ping @caojoshua (or anyone else that understand what's going on)

llvm/lib/Analysis/ScalarEvolution.cpp

case scAddRecExpr: {
     }
 
     // TODO: non-affine addrec
     if (AddRec->isAffine()) {
       const SCEV *MaxBEScev =
           getConstantMaxBackedgeTakenCount(AddRec->getLoop());
       if (!isa<SCEVCouldNotCompute>(MaxBEScev)) {
         APInt MaxBECount = cast<SCEVConstant>(MaxBEScev)->getAPInt();
-        if (MaxBECount.getBitWidth() < BitWidth)
+
+        // Adjust MaxBECount to the same bitwidth as AddRec. We can truncate if
+        // MaxBECount's active bits are all <= AddRec's bit width.
+        if (MaxBECount.getBitWidth() > BitWidth &&
+            MaxBECount.getActiveBits() <= BitWidth)
+          MaxBECount = MaxBECount.trunc(BitWidth);
+        else if (MaxBECount.getBitWidth() < BitWidth)
           MaxBECount = MaxBECount.zext(BitWidth);
+
         if (MaxBECount.getBitWidth() == BitWidth) {
           auto RangeFromAffine = getRangeForAffineAR(
               AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
           ConservativeResult =
               ConservativeResult.intersectWith(RangeFromAffine, RangeType);
 
           auto RangeFromFactoring = getRangeViaFactoring(
               AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
           ConservativeResult =
               ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
         }
       }
 
       // Now try symbolic BE count and more powerful methods.
       if (UseExpensiveRangeSharpening) {
         const SCEV *SymbolicMaxBECount =
             getSymbolicMaxBackedgeTakenCount(AddRec->getLoop());

llvm/test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll

 @a = global [10004 x [10004 x i32]] zeroinitializer, align 16
 
 ; Function Attrs: nounwind uwtable
 define void @coupled_miv_type_mismatch(i32 %n) #0 {
 ; DELIN-LABEL: 'Dependence Analysis' for function 'coupled_miv_type_mismatch'
 entry:
   br label %for.cond
 
-; DELIN: da analyze - input [* *]!
-; DELIN: da analyze - anti [* *|<]!
+; DELIN: da analyze - none!
+; DELIN: da analyze - consistent anti [1 -2]!
 ; DELIN: da analyze - none!
 for.cond:                                         ; preds = %for.inc11, %entry
   %indvars.iv11 = phi i64 [ %indvars.iv.next12, %for.inc11 ], [ 1, %entry ]
   %exitcond14 = icmp ne i64 %indvars.iv11, 10000
   br i1 %exitcond14, label %for.cond1.preheader, label %for.end13
 
 for.cond1.preheader:                              ; preds = %for.cond
   %0 = trunc i64 %indvars.iv11 to i32

llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll

 ; CHECK-NEXT:    --> %start U: [0,128) S: [0,128)
 ; CHECK-NEXT:    %step = select i1 %c, i32 -1, i32 1
 ; CHECK-NEXT:    --> %step U: [1,0) S: [-2,2)
 ; CHECK-NEXT:    %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,128) S: [0,128) Exits: 127 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {%start,+,%step}<nsw><%loop> U: [0,128) S: [0,128) Exits: ((127 * %step)<nsw> + %start) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.trunc = trunc i32 %iv to i16
-; CHECK-NEXT:    --> {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: full-set S: full-set Exits: ((trunc i32 %start to i16) + (127 * (trunc i32 %step to i16))<nsw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: [0,128) S: [0,128) Exits: ((trunc i32 %start to i16) + (127 * (trunc i32 %step to i16))<nsw>) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add i32 %iv, %step
 ; CHECK-NEXT:    --> {(%step + %start),+,%step}<nw><%loop> U: [-256,256) S: [-256,256) Exits: ((128 * %step)<nsw> + %start) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %loop.iv.inc = add i32 %loop.iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,129) S: [1,129) Exits: 128 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @f4
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 127
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 127
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 127
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 127
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 128
 ;
 
-; @f4() demonstrates a case where SCEV is not able to compute a
-; precise range for %iv.trunc, though it should be able to, in theory.
-; This is because SCEV looks into affine add recurrences only when the
-; backedge taken count of the loop has the same bitwidth as the
-; induction variable.
 entry:
   %start = select i1 %c, i32 127, i32 0
   %step  = select i1 %c, i32 -1,  i32 1
   br label %loop
 
 loop:
   %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ]
   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]

llvm/test/Analysis/ScalarEvolution/limit-depth.ll

 exit:
   %ze2 = zext i64 %iv2.inc to i128
   ret void
 }
 
 define void @test_trunc(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f) {
 ; CHECK-LABEL: @test_trunc
 ; CHECK:          %trunc2 = trunc i64 %iv2.inc to i32
-; CHECK-NEXT:     -->  {(trunc i64 (1 + {7,+,1}<%loop>) to i32),+,1}<%loop2>
+; CHECK-NEXT:     -->  {(trunc i64 (1 + {7,+,1}<%loop>)<nuw><nsw> to i32),+,1}<%loop2> U: [8,53) S: [8,53)  -->  52 U: [52,53) S: [52,53)
 entry:
   br label %loop
 
 loop:
   %iv = phi i128 [ 6, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add nsw i128 %iv, 1
   %cond = icmp sle i128 %iv.inc, 50
   br i1 %cond, label %loop, label %between

llvm/test/Analysis/ScalarEvolution/nsw.ll

 define i32 @PR12375(ptr readnone %arg) {
 ; CHECK-LABEL: 'PR12375'
 ; CHECK-NEXT:  Classifying expressions for: @PR12375
 ; CHECK-NEXT:    %tmp = getelementptr inbounds i32, ptr %arg, i64 2
 ; CHECK-NEXT:    --> (8 + %arg)<nuw> U: [8,0) S: [8,0)
 ; CHECK-NEXT:    %tmp2 = phi ptr [ %arg, %bb ], [ %tmp5, %bb1 ]
 ; CHECK-NEXT:    --> {%arg,+,4}<nuw><%bb1> U: full-set S: full-set Exits: (4 + %arg)<nuw> LoopDispositions: { %bb1: Computable }
 ; CHECK-NEXT:    %tmp3 = phi i32 [ 0, %bb ], [ %tmp4, %bb1 ]
-; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%bb1> U: [0,-2147483648) S: [0,-2147483648) Exits: 1 LoopDispositions: { %bb1: Computable }
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%bb1> U: [0,2) S: [0,2) Exits: 1 LoopDispositions: { %bb1: Computable }
 ; CHECK-NEXT:    %tmp4 = add nsw i32 %tmp3, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%bb1> U: [1,0) S: [1,0) Exits: 2 LoopDispositions: { %bb1: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%bb1> U: [1,3) S: [1,3) Exits: 2 LoopDispositions: { %bb1: Computable }
 ; CHECK-NEXT:    %tmp5 = getelementptr inbounds i32, ptr %tmp2, i64 1
 ; CHECK-NEXT:    --> {(4 + %arg)<nuw>,+,4}<nuw><%bb1> U: [4,0) S: [4,0) Exits: (8 + %arg)<nuw> LoopDispositions: { %bb1: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @PR12375
 ; CHECK-NEXT:  Loop %bb1: backedge-taken count is 1
 ; CHECK-NEXT:  Loop %bb1: constant max backedge-taken count is 1
 ; CHECK-NEXT:  Loop %bb1: symbolic max backedge-taken count is 1
 ; CHECK-NEXT:  Loop %bb1: Predicated backedge-taken count is 1
 ; CHECK-NEXT:   Predicates:

llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll

 
 declare void @llvm.assume(i1)
 
 ; Test case for PR57818.
 define void @step_is_neg_addrec_slt_8(i64 %n) {
 ; CHECK-LABEL: 'step_is_neg_addrec_slt_8'
 ; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_slt_8
 ; CHECK-NEXT:  Loop %inner: backedge-taken count is (7 /u {0,+,-1}<nuw><nsw><%outer.header>)
-; CHECK-NEXT:  Loop %inner: constant max backedge-taken count is -2147483640
+; CHECK-NEXT:  Loop %inner: constant max backedge-taken count is 8
 ; CHECK-NEXT:  Loop %inner: symbolic max backedge-taken count is (7 /u {0,+,-1}<nuw><nsw><%outer.header>)
 ; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is (7 /u {0,+,-1}<nuw><nsw><%outer.header>)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %inner: Trip multiple is 1
 ; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: constant max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: symbolic max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0

 
 exit:
   ret void
 }
 
 define void @step_is_neg_addrec_slt_var(i32 %n) {
 ; CHECK-LABEL: 'step_is_neg_addrec_slt_var'
 ; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_slt_var
-; CHECK-NEXT:  Loop %inner: backedge-taken count is ((((-1 * (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))<nuw><nsw> + {0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n)) /u (1 umax {0,+,-1}<nuw><nsw><%outer.header>)) + (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))
-; CHECK-NEXT:  Loop %inner: constant max backedge-taken count is -1
-; CHECK-NEXT:  Loop %inner: symbolic max backedge-taken count is ((((-1 * (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))<nuw><nsw> + {0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n)) /u (1 umax {0,+,-1}<nuw><nsw><%outer.header>)) + (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))
-; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is ((((-1 * (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))<nuw><nsw> + {0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n)) /u (1 umax {0,+,-1}<nuw><nsw><%outer.header>)) + (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))
+; CHECK-NEXT:  Loop %inner: backedge-taken count is ({0,+,1}<nuw><nsw><%outer.header> + ({0,+,-1}<nsw><%outer.header> smax %n))
+; CHECK-NEXT:  Loop %inner: constant max backedge-taken count is 2147483647
+; CHECK-NEXT:  Loop %inner: symbolic max backedge-taken count is ({0,+,1}<nuw><nsw><%outer.header> + ({0,+,-1}<nsw><%outer.header> smax %n))
+; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is ({0,+,1}<nuw><nsw><%outer.header> + ({0,+,-1}<nsw><%outer.header> smax %n))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %inner: Trip multiple is 1
 ; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: constant max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: symbolic max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %outer.header: Trip multiple is 1

 
 exit:
   ret void
 }
 
 define void @step_is_neg_addrec_unknown_start(i32 %n) {
 ; CHECK-LABEL: 'step_is_neg_addrec_unknown_start'
 ; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_unknown_start
-; CHECK-NEXT:  Loop %inner: backedge-taken count is ((((-1 * (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))<nuw><nsw> + {(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>)) /u (1 umax {0,+,-1}<%outer.header>)) + (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))
+; CHECK-NEXT:  Loop %inner: backedge-taken count is ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nsw><%outer.header>))
 ; CHECK-NEXT:  Loop %inner: constant max backedge-taken count is -2147483640
-; CHECK-NEXT:  Loop %inner: symbolic max backedge-taken count is ((((-1 * (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))<nuw><nsw> + {(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>)) /u (1 umax {0,+,-1}<%outer.header>)) + (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))
-; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is ((((-1 * (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))<nuw><nsw> + {(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>)) /u (1 umax {0,+,-1}<%outer.header>)) + (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))
+; CHECK-NEXT:  Loop %inner: symbolic max backedge-taken count is ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nsw><%outer.header>))
+; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nsw><%outer.header>))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %inner: Trip multiple is 1
 ; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: constant max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: symbolic max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %outer.header: Trip multiple is 1

polly/test/CodeGen/switch-in-non-affine-region.ll

 ; RUN: opt %loadPolly \
 ; RUN: -S -polly-codegen < %s | FileCheck %s
 ;
 ;    void f(int *A, int N) {
 ;      for (int i = 0; i < N; i++)
 ;        if (A[i])
 ;          switch (i % 4) {
 ;          case 0:
 ;            A[i] += 1;
 ;            break;
 ;          case 1:
 ;            A[i] += 2;
 ;            break;
 ;          }
 ;    }
 ;
-; CHECK: polly.stmt.if.then:
-; CHECK:   %[[trunc:.*]] = trunc i64 %polly.indvar to i32
-; CHECK:   %p_rem = srem i32 %[[trunc]], 4
-; CHECK:   switch i32 %p_rem, label %polly.stmt.sw.epilog [
-; CHECK:     i32 0, label %polly.stmt.sw.bb
-; CHECK:     i32 1, label %polly.stmt.sw.bb.3
-; CHECK:   ]
+; CHECK:      polly.stmt.if.then:
+; CHECK-NEXT:   %2 = trunc i64 %polly.indvar to i2
+; CHECK-NEXT:   %3 = zext i2 %2 to i32
+; CHECK-NEXT:   switch i32 %3, label %polly.stmt.sw.epilog [
+; CHECK-NEXT:     i32 0, label %polly.stmt.sw.bb
+; CHECK-NEXT:     i32 1, label %polly.stmt.sw.bb.3
+; CHECK-NEXT:   ]
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(ptr %A, i32 %N) {
 entry:
   %tmp = sext i32 %N to i64
   br label %for.cond
 

polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll

 ; RUN: opt %loadPolly -basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=false                       -polly-print-scops -disable-output < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true                        -polly-print-scops -disable-output < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -polly-allow-nonaffine -polly-print-scops -disable-output < %s | FileCheck %s --check-prefix=ALL
 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always model the
 ; innermost loop as a SCoP of depth 1, we can overapproximate the
 ; innermost loop in the whole loop nest and model A[k] as a non-affine
 ; access.
 ;
 ; INNERMOST:      Function: f
 ; INNERMOST-NEXT: Region: %bb15---%bb13
 ; INNERMOST-NEXT: Max Loop Depth:  1
 ; INNERMOST-NEXT: Invariant Accesses: {
 ; INNERMOST-NEXT: }
 ; INNERMOST-NEXT: Context:
-; INNERMOST-NEXT: [p_0, p_1, p_2] -> {  : 0 <= p_0 <= 2147483647 and 0 <= p_1 <= 1024 and 0 <= p_2 <= 1024 }
+; INNERMOST-NEXT: [p_0, p_1, p_2] -> {  : 0 <= p_0 <= 1048576 and 0 <= p_1 <= 1024 and 0 <= p_2 <= 1024 }
 ; INNERMOST-NEXT: Assumed Context:
 ; INNERMOST-NEXT: [p_0, p_1, p_2] -> {  :  }
 ; INNERMOST-NEXT: Invalid Context:
 ; INNERMOST-NEXT: [p_0, p_1, p_2] -> {  : false }
 ; INNERMOST:      p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
 ; INNERMOST-NEXT: p1: {0,+,1}<nuw><nsw><%bb11>
 ; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb13>
 ; INNERMOST-NEXT: Arrays {

 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };
 ; ALL-NEXT:         Schedule :=
 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> [i0, i1] };
 ; ALL-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[i0] };
 ; ALL-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[i1] };
 ; ALL-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
-; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 2147483647 };
+; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 1048576 };
 ; ALL-NEXT:         MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
-; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 2147483647 };
+; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 1048576 };
 ; ALL-NEXT: }
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        for (int j = 0; j < 1024; j++)
 ;          for (int k = 0; k < i * j; k++)
 ;            A[k] += A[i] + A[j];
 ;    }