[Polly] Generate more 'canonical' induction variable if we can prove there is no overflow.

[etherzhhb]

Summary

Today Polly generates induction variable in this way:

polly.indvar = phi 0, polly.indvar.next
...
polly.indvar.next = polly.indvar + stide
polly.loop_cond = predicate polly.indvar, (UB - stride)

Instead of:

polly.indvar = phi 0, polly.indvar.next
...
polly.indvar.next = polly.indvar + stide
polly.loop_cond = predicate polly.indvar.next, UB

The way Polly generate induction variable cause some problem in the indvar simplify pass.
This patch make polly generate the later form if possible

[grosser]

I don't think checking with mayOverflowOnIV is needed. The types we use today are anyway just a guess, as we have no idea what type is needed. Consequently checking for possible overflows -- while we already may have some overflows just gives a wrong sense of security.

I think we should work towards what we want:

1. code that matches what indvars would like to see
2. code that is typesafe

Dropping this surprising subtract goes towards 1). Maximilian worked in his bachelor thesis on deriving precise types for the ASTs we generate. As a result of this work, he will derive a type that is large enough to contain UB, LB, as well as UB + Stride. Hence, as soon as his code is upstreamed, the code produced after this patch is valid. Hence, I would just add a comment at the top of this function, that we expect the type of UB, LB, UB+Stride to be large enough for values that UB may take throughout the execution of the loop, including the computation of indvar + Stride before the final abort..

[grosser]

I just posted to bug reports that cover are not directly related to this patch, but touch a very similar topic: http://llvm.org/PR32997, http://llvm.org/PR32998

[etherzhhb]

Address Tobias's comment

[etherzhhb]

Fix typo

[grosser]

LGTM, assuming you update the commit message accordingly.

lib/CodeGen/LoopGenerators.cpp

26 ↗

(On Diff #98649)

No need for these includes any more.

polly/trunk/lib/CodeGen/LoopGenerators.cpp

 //===----------------------------------------------------------------------===//
 
 #include "polly/CodeGen/LoopGenerators.h"
 #include "polly/ScopDetection.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 using namespace polly;
+using namespace PatternMatch;
 
 static cl::opt<int>
     PollyNumThreads("polly-num-threads",
                     cl::desc("Number of threads to use (0 = auto)"), cl::Hidden,
                     cl::init(0));
 
 // We generate a loop of either of the following structures:
 //

 //              ExitBB                         ExitBB
 //
 // depending on whether or not we know that it is executed at least once. If
 // not, GuardBB checks if the loop is executed at least once. If this is the
 // case we branch to PreHeaderBB and subsequently to the HeaderBB, which
 // contains the loop iv 'polly.indvar', the incremented loop iv
 // 'polly.indvar_next' as well as the condition to check if we execute another
 // iteration of the loop. After the loop has finished, we branch to ExitBB.
+// We expect the type of UB, LB, UB+Stride to be large enough for values that
+// UB may take throughout the execution of the loop, including the computation
+// of indvar + Stride before the final abort.
 Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
                          PollyIRBuilder &Builder, LoopInfo &LI,
                          DominatorTree &DT, BasicBlock *&ExitBB,
                          ICmpInst::Predicate Predicate,
                          ScopAnnotator *Annotator, bool Parallel,
                          bool UseGuard) {
   Function *F = Builder.GetInsertBlock()->getParent();
   LLVMContext &Context = F->getContext();
Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
 
   // HeaderBB
   DT.addNewBlock(HeaderBB, PreHeaderBB);
   Builder.SetInsertPoint(HeaderBB);
   PHINode *IV = Builder.CreatePHI(LoopIVType, 2, "polly.indvar");
   IV->addIncoming(LB, PreHeaderBB);
   Stride = Builder.CreateZExtOrBitCast(Stride, LoopIVType);
   Value *IncrementedIV = Builder.CreateNSWAdd(IV, Stride, "polly.indvar_next");
-  Value *LoopCondition;
-  UB = Builder.CreateSub(UB, Stride, "polly.adjust_ub");
-  LoopCondition = Builder.CreateICmp(Predicate, IV, UB);
-  LoopCondition->setName("polly.loop_cond");
+  Value *LoopCondition =
+      Builder.CreateICmp(Predicate, IncrementedIV, UB, "polly.loop_cond");
 
   // Create the loop latch and annotate it as such.
   BranchInst *B = Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
   if (Annotator)
     Annotator->annotateLoopLatch(B, NewLoop, Parallel);
 
   IV->addIncoming(IncrementedIV, HeaderBB);
   if (GuardBB)

polly/trunk/test/Isl/CodeGen/LoopParallelMD/loop_nest_param_parallel.ll

 ; RUN: opt %loadPolly -polly-codegen -polly-ast-detect-parallel -S < %s | FileCheck %s
 ;
 ; Check that we mark multiple parallel loops correctly including the memory instructions.
 ;
-; CHECK-DAG:  %polly.loop_cond[[COuter:[0-9]*]] = icmp sle i64 %polly.indvar{{[0-9]*}}, 1022
+; CHECK-DAG:  %polly.loop_cond[[COuter:[0-9]*]] = icmp sle i64 %polly.indvar_next{{[0-9]*}}, 1023
 ; CHECK-DAG:  br i1 %polly.loop_cond[[COuter]], label %polly.loop_header{{[0-9]*}}, label %polly.loop_exit{{[0-9]*}}, !llvm.loop ![[IDOuter:[0-9]*]]
 ;
-; CHECK-DAG:  %polly.loop_cond[[CInner:[0-9]*]] = icmp sle i64 %polly.indvar{{[0-9]*}}, 510
+; CHECK-DAG:  %polly.loop_cond[[CInner:[0-9]*]] = icmp sle i64 %polly.indvar_next{{[0-9]*}}, 511
 ; CHECK-DAG:  br i1 %polly.loop_cond[[CInner]], label %polly.loop_header{{[0-9]*}}, label %polly.loop_exit{{[0-9]*}}, !llvm.loop ![[IDInner:[0-9]*]]
 ;
 ; CHECK-DAG: store i32 %{{[a-z_0-9]*}}, i32* %{{[a-z_0-9]*}}, {{[ ._!,a-zA-Z0-9]*}}, !llvm.mem.parallel_loop_access !4
 ;
 ; CHECK-DAG: ![[IDOuter]] = distinct !{![[IDOuter]]}
 ; CHECK-DAG: ![[IDInner]] = distinct !{![[IDInner]]}
 ; CHECK-DAG: !4 = !{![[IDOuter]], ![[IDInner]]}
 ;

polly/trunk/test/Isl/CodeGen/MemAccess/generate-all.ll

 
 ; SCEV:      polly.stmt.bb2:                                   ; preds = %polly.loop_header
 ; SCEV-NEXT:   %p_tmp = srem i64 %polly.indvar, 4
 ; SCEV-NEXT:   %p_tmp3 = getelementptr inbounds float, float* %A, i64 %p_tmp
 ; SCEV-NEXT:   %tmp4_p_scalar_ = load float, float* %p_tmp3, align 4, !alias.scope !0, !noalias !2
 ; SCEV-NEXT:   %p_tmp5 = fadd float %tmp4_p_scalar_, 1.000000e+01
 ; SCEV-NEXT:   store float %p_tmp5, float* %p_tmp3, align 4, !alias.scope !0, !noalias !2
 ; SCEV-NEXT:   %polly.indvar_next = add nsw i64 %polly.indvar, 1
-; SCEV-NEXT:   %polly.loop_cond = icmp sle i64 %polly.indvar, 98
+; SCEV-NEXT:   %polly.loop_cond = icmp sle i64 %polly.indvar_next, 99
 ; SCEV-NEXT:   br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
 
 ; ASTEXPR:  polly.stmt.bb2:                                   ; preds = %polly.loop_header
 ; ASTEXPR-NEXT:   %pexp.pdiv_r = urem i64 %polly.indvar, 4
 ; ASTEXPR-NEXT:   %polly.access.A = getelementptr float, float* %A, i64 %pexp.pdiv_r
 ; ASTEXPR-NEXT:   %tmp4_p_scalar_ = load float, float* %polly.access.A, align 4, !alias.scope !0, !noalias !2
 ; ASTEXPR-NEXT:   %p_tmp5 = fadd float %tmp4_p_scalar_, 1.000000e+01
 ; ASTEXPR-NEXT:   %pexp.pdiv_r1 = urem i64 %polly.indvar, 4
 ; ASTEXPR-NEXT:   %polly.access.A2 = getelementptr float, float* %A, i64 %pexp.pdiv_r1
 ; ASTEXPR-NEXT:   store float %p_tmp5, float* %polly.access.A2, align 4, !alias.scope !0, !noalias !2
 ; ASTEXPR-NEXT:   %polly.indvar_next = add nsw i64 %polly.indvar, 1
-; ASTEXPR-NEXT:   %polly.loop_cond = icmp sle i64 %polly.indvar, 98
+; ASTEXPR-NEXT:   %polly.loop_cond = icmp sle i64 %polly.indvar_next, 99
 ; ASTEXPR-NEXT:   br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @foo(float* %A) {
 bb:
   br label %bb1
 

polly/trunk/test/Isl/CodeGen/MemAccess/update_access_functions.ll

 ; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S \
 ; RUN:                -polly-import-jscop-postfix=transformed -polly-codegen \
 ; RUN:                 < %s -S | FileCheck %s
 
 ; CHECK-LABEL: polly.stmt.loop1:
-; CHECK-NEXT:   %3 = mul nsw i64 5, %polly.indvar
+; CHECK-NEXT:   %3 = mul nsw i64 5, %polly.indvar{{[0-9]*}}
 ; CHECK-NEXT:   %4 = sub nsw i64 %3, 10
 ; CHECK-NEXT:   %polly.access.A = getelementptr double, double* %A, i64 %4
 ; CHECK-NEXT:   store double 4.200000e+01, double* %polly.access.A, align 8
 
 ; CHECK-LABEL: polly.stmt.loop2:
-; CHECK-NEXT:   %polly.access.A10 = getelementptr double, double* %A, i64 42
-; CHECK-NEXT:   %val_p_scalar_ = load double, double* %polly.access.A10, align 8
+; CHECK-NEXT:   %polly.access.A[[Num0:[0-9]*]] = getelementptr double, double* %A, i64 42
+; CHECK-NEXT:   %val_p_scalar_ = load double, double* %polly.access.A[[Num0]], align 8
 
 ; CHECK-LABEL: polly.stmt.loop3:
 ; CHECK-NEXT:   %val.s2a.reload = load double, double* %val.s2a
-; CHECK-NEXT:   [[REG0:%.*]] = mul nsw i64 13, %polly.indvar16
+; CHECK-NEXT:   [[REG0:%.*]] = mul nsw i64 13, %polly.indvar{{[0-9]*}}
 ; CHECK-NEXT:   [[REG1:%.*]] = add nsw i64 [[REG0]], 5
-; CHECK-NEXT:   %polly.access.A20 = getelementptr double, double* %A, i64 [[REG1]]
-; CHECK-NEXT:   store double %val.s2a.reload, double* %polly.access.A20, align 8,
+; CHECK-NEXT:   %polly.access.A[[Num1:[0-9]*]] = getelementptr double, double* %A, i64 [[REG1]]
+; CHECK-NEXT:   store double %val.s2a.reload, double* %polly.access.A[[Num1]], align 8,
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @update_access_functions(i64 %arg, double* %A) {
 bb3:
   br label %loop1
 
 loop1:

polly/trunk/test/Isl/CodeGen/OpenMP/single_loop.ll

 ; IR-LABEL: polly.loop_header:
 ; IR-NEXT:   %polly.indvar = phi i64 [ %polly.par.LB, %polly.loop_preheader ], [ %polly.indvar_next, %polly.stmt.S ]
 ; IR-NEXT:   br label %polly.stmt.S
 
 ; IR-LABEL: polly.stmt.S:
 ; IR-NEXT:   %[[gep:[._a-zA-Z0-9]*]] = getelementptr [1024 x float], [1024 x float]* {{.*}}, i64 0, i64 %polly.indvar
 ; IR-NEXT:   store float 1.000000e+00, float* %[[gep]]
 ; IR-NEXT:   %polly.indvar_next = add nsw i64 %polly.indvar, 1
-; IR-NEXT:   %polly.adjust_ub = sub i64 %polly.par.UBAdjusted, 1
-; IR-NEXT:   %polly.loop_cond = icmp sle i64 %polly.indvar, %polly.adjust_ub
+; IR-NEXT:   %polly.loop_cond = icmp sle i64 %polly.indvar_next, %polly.par.UBAdjusted
 ; IR-NEXT:   br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
 
 ; IR-LABEL: polly.loop_preheader:
 ; IR-NEXT:   br label %polly.loop_header
 
 ; IR: attributes #1 = { "polly.skip.fn" }
 
 ; IR-STRIDE4:   call void @GOMP_parallel_loop_runtime_start(void (i8*)* @single_parallel_loop_polly_subfn, i8* %polly.par.userContext1, i32 0, i64 0, i64 1024, i64 4)

polly/trunk/test/Isl/CodeGen/non_affine_float_compare.ll

 ; CHECK:   br label %polly.stmt.bb12
 
 ; CHECK: polly.stmt.bb12:
 ; CHECK:   %scevgep[[R4:[0-9]*]] = getelementptr float, float* %A, i64 %polly.indvar
 ; CHECK:   %tmp10b_p_scalar_ = load float, float* %scevgep[[R4]], align 4, !alias.scope !0, !noalias !2
 ; CHECK:   %p_tmp11b = fadd float %tmp10b_p_scalar_, 1.000000e+00
 ; CHECK:   store float %p_tmp11b, float* %scevgep[[R4]], align 4, !alias.scope !0, !noalias !2
 ; CHECK:   %polly.indvar_next = add nsw i64 %polly.indvar, 1
-; CHECK:   %polly.loop_cond = icmp sle i64 %polly.indvar, 1022
+; CHECK:   %polly.loop_cond = icmp sle i64 %polly.indvar_next, 1023
 ; CHECK:   br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(float* %A) {
 bb:
   br label %bb1
 

polly/trunk/test/Isl/CodeGen/phi_scalar_simple_2.ll

 ; CHECK-LABEL: polly.merge_new_and_old:
 ; CHECK:         %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.exiting ], [ %x.addr.0, %for.cond ]
 ; CHECK:         ret i32 %x.addr.0.merge
 
 ; CHECK-LABEL: polly.start:
 ; CHECK-NEXT:    store i32 %x, i32* %x.addr.0.phiops
 ; CHECK-NEXT:    sext
 
-; CHECK-LABEL: polly.merge21:
+; CHECK-LABEL: polly.merge{{[a-z_0-9]*}}:
 ; CHECK:         %x.addr.0.final_reload = load i32, i32* %x.addr.0.s2a
 
 for.cond:                                         ; preds = %for.inc5, %entry
 ; CHECK-LABEL: polly.stmt.for.cond{{[0-9]*}}:
 ; CHECK:         %x.addr.0.phiops.reload[[R1:[0-9]*]] = load i32, i32* %x.addr.0.phiops
 ; CHECK:         store i32 %x.addr.0.phiops.reload[[R1]], i32* %x.addr.0.s2a
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc5 ], [ 0, %entry ]
   %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1, %for.inc5 ]

polly/trunk/test/Isl/single_loop_param_less_equal.ll

 ; CODEGEN: polly.loop_header:
 ; CODEGEN:   %polly.indvar = phi i64 [ 0, %polly.loop_preheader ], [ %polly.indvar_next, %polly.stmt.loop.body ]
 ; CODEGEN:   br label %polly.stmt.loop.body
 
 ; CODEGEN: polly.stmt.loop.body:
 ; CODEGEN:   [[PTR:%[a-zA-Z0-9_\.]+]] = getelementptr [1024 x i32], [1024 x i32]* @A, i64 0, i64 %polly.indvar
 ; CODEGEN:   store i32 1, i32* [[PTR]]
 ; CODEGEN:   %polly.indvar_next = add nsw i64 %polly.indvar, 1
-; CODEGEN:   %polly.adjust_ub = sub i64 %n, 1
-; CODEGEN:   %polly.loop_cond = icmp sle i64 %polly.indvar, %polly.adjust_ub
+; CODEGEN:   %polly.loop_cond = icmp sle i64 %polly.indvar_next, %n
 ; CODEGEN:   br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
 
 ; CODEGEN: polly.loop_preheader:
 ; CODEGEN:   br label %polly.loop_header
 
 ; LOOPS: Loop at depth 1 containing: %loop.header<header><exiting>,%loop.body,%loop.backedge<latch>
 ; LOOPS: Loop at depth 1 containing: %polly.loop_header<header>,%polly.stmt.loop.body<latch><exiting>

polly/trunk/test/Isl/single_loop_param_less_than.ll

 ; CODEGEN: polly.loop_header:
 ; CODEGEN:   %polly.indvar = phi i64 [ 0, %polly.loop_preheader ], [ %polly.indvar_next, %polly.stmt.loop.body ]
 ; CODEGEN:   br label %polly.stmt.loop.body
 
 ; CODEGEN: polly.stmt.loop.body:
 ; CODEGEN:   [[PTR:%[a-zA-Z0-9_\.]+]] =  getelementptr [1024 x i32], [1024 x i32]* @A, i64 0, i64 %polly.indvar
 ; CODEGEN:   store i32 1, i32* [[PTR]]
 ; CODEGEN:   %polly.indvar_next = add nsw i64 %polly.indvar, 1
-; CODEGEN:   %polly.adjust_ub = sub i64 %n, 1
-; CODEGEN:   %polly.loop_cond = icmp slt i64 %polly.indvar, %polly.adjust_ub
+; CODEGEN:   %polly.loop_cond = icmp slt i64 %polly.indvar_next, %n
 ; CODEGEN:   br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
 
 ; CODEGEN: polly.loop_preheader:
 ; CODEGEN:   br label %polly.loop_header

polly/trunk/test/ScheduleOptimizer/pattern-matching-based-opts_10.ll

 ; RUN: opt %loadPolly -polly-opt-isl -polly-invariant-load-hoisting=true \
 ; RUN: -polly-pattern-matching-based-opts=true \
 ; RUN: -polly-target-throughput-vector-fma=1 \
 ; RUN: -polly-target-latency-vector-fma=1 \
 ; RUN: -polly-codegen -polly-target-1st-cache-level-associativity=8 \
 ; RUN: -polly-target-2nd-cache-level-associativity=8 \
 ; RUN: -polly-target-1st-cache-level-size=32768 \
 ; RUN: -polly-target-vector-register-bitwidth=256 \
 ; RUN: -polly-target-2nd-cache-level-size=262144 -S < %s \
 ; RUN: | FileCheck %s
 ;
 ; This test case checks whether Polly generates second level alias metadata
 ; to distinguish the specific accesses in case of the ublas gemm kernel.
 ;
-; CHECK: %tmp22_p_scalar_ = load double, double* %scevgep168, align 8, !alias.scope !10, !noalias !2
-; CHECK: store double %p_tmp23, double* %scevgep168, align 8, !alias.scope !10, !noalias !2
-; CHECK: %tmp22_p_scalar_188 = load double, double* %scevgep187, align 8, !alias.scope !11, !noalias !12
-; CHECK: store double %p_tmp23189, double* %scevgep187, align 8, !alias.scope !11, !noalias !12
-; CHECK: %tmp22_p_scalar_209 = load double, double* %scevgep208, align 8, !alias.scope !13, !noalias !14
-; CHECK: store double %p_tmp23210, double* %scevgep208, align 8, !alias.scope !13, !noalias !14
-; CHECK: %tmp22_p_scalar_230 = load double, double* %scevgep229, align 8, !alias.scope !15, !noalias !16
-; CHECK: store double %p_tmp23231, double* %scevgep229, align 8, !alias.scope !15, !noalias !16
+; CHECK: %tmp22_p_scalar_{{[0-9]*}} = load double, double* %scevgep[[N0:[a-z_0-9]*]], align 8, !alias.scope !10, !noalias !2
+; CHECK: store double %p_tmp23{{[0-9]*}}, double* %scevgep[[N0]], align 8, !alias.scope !10, !noalias !2
+; CHECK: %tmp22_p_scalar_{{[0-9]*}} = load double, double* %scevgep[[N1:[a-z_0-9]*]], align 8, !alias.scope !11, !noalias !12
+; CHECK: store double %p_tmp23{{[0-9]*}}, double* %scevgep[[N1]], align 8, !alias.scope !11, !noalias !12
+; CHECK: %tmp22_p_scalar_{{[0-9]*}} = load double, double* %scevgep[[N2:[a-z_0-9]*]], align 8, !alias.scope !13, !noalias !14
+; CHECK: store double %p_tmp23{{[0-9]*}}, double* %scevgep[[N2]], align 8, !alias.scope !13, !noalias !14
+; CHECK: %tmp22_p_scalar_{{[0-9]*}} = load double, double* %scevgep[[N3:[a-z_0-9]*]], align 8, !alias.scope !15, !noalias !16
+; CHECK: store double %p_tmp23{{[0-9]*}}, double* %scevgep[[N3]], align 8, !alias.scope !15, !noalias !16
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-unknown"
 
 define internal void @kernel_gemm(i32 %arg, i32 %arg1, i32 %arg2, double %arg3, double %arg4, [1056 x double]* %arg5, [1024 x double]* %arg6, [1056 x double]* %arg7) {
 bb:
   br label %bb8