Extended Description

Wrong scheduling occurs when passing polly-opt-max-coefficient=-1 and and -polly-opt-simplify-deps=no.

Below is the test,

define i32 @​foo(i32* nocapture readonly %A) #​0 {
entry:
%add9.lcssa.lcssa.reg2mem = alloca i32
%s.124.reg2mem = alloca i32
%s.226.reg2mem = alloca i32
br label %entry.split

entry.split: ; preds = %entry
br label %for.cond1.preheader

for.cond1.preheader: ; preds = %entry.split, %for.inc13
%i.028 = phi i32 [ 0, %entry.split ], [ %inc14, %for.inc13 ]
store i32 0, i32* %s.124.reg2mem
br label %for.body3

for.body3: ; preds = %for.cond1.preheader, %for.body3
%j.025 = phi i32 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
%s.124.reload = load i32* %s.124.reg2mem
%arrayidx = getelementptr inbounds i32* %A, i32 %j.025
%0 = load i32* %arrayidx, align 4
%add = add nsw i32 %s.124.reload, %0
%inc = add nsw i32 %j.025, 1
%cmp2 = icmp slt i32 %inc, 12
store i32 %add, i32* %s.124.reg2mem
br i1 %cmp2, label %for.body3, label %for.body7.preheader

for.body7.preheader: ; preds = %for.body3
%1 = load i32* %s.124.reg2mem
store i32 %1, i32* %s.226.reg2mem
br label %for.body7

for.body7: ; preds = %for.body7.preheader, %for.body7
%j4.027 = phi i32 [ %inc11, %for.body7 ], [ 0, %for.body7.preheader ]
%s.226.reload = load i32* %s.226.reg2mem
%arrayidx8 = getelementptr inbounds i32* %A, i32 %j4.027
%2 = load i32* %arrayidx8, align 4
%add9 = add nsw i32 %s.226.reload, %2
%inc11 = add nsw i32 %j4.027, 1
%cmp6 = icmp slt i32 %inc11, 12
store i32 %add9, i32* %s.226.reg2mem
br i1 %cmp6, label %for.body7, label %for.inc13

for.inc13: ; preds = %for.body7
%3 = load i32* %s.226.reg2mem
%inc14 = add nsw i32 %i.028, 1
%cmp = icmp slt i32 %inc14, 2
store i32 %3, i32* %add9.lcssa.lcssa.reg2mem
br i1 %cmp, label %for.cond1.preheader, label %for.end15

for.end15: ; preds = %for.inc13
%add9.lcssa.lcssa.reload = load i32* %add9.lcssa.lcssa.reg2mem
ret i32 %add9.lcssa.lcssa.reload
}

opt -basicaa -polly -polly-ast-detect-parallel -polly-vectorizer=none -polly-opt-isl -polly-codegen-isl -polly-opt-max-coefficient=-1 -polly-opt-simplify-deps=no < bug1.ll -debug 2>debug.txt
grep -A 25 "isl ast" debug.txt

:: isl ast :: foo :: for.cond1.preheader => for.end15
{ : }
{ Stmt_for_inc13[i0] -> [1, 11 + 11i0, 0] : i0 >= 0 and i0 <= 1; Stmt_for_body7[i0, i1] -> [i0, 11 + i1, 0] : i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 11; Stmt_for_body3[i0, i1] -> [i0, i1, 0] : i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 11; Stmt_for_cond1_preheader[i0] -> [0, 11i0, 0] : i0 >= 0 and i0 <= 1; Stmt_for_body7_preheader[i0] -> [i0, 11, 0] : i0 >= 0 and i0 <= 1 }
if (1)

#pragma minimal dependence distance: 1
for (int c0 = 0; c0 <= 1; c0 += 1) {
  #pragma minimal dependence distance: 1
  for (int c1 = 0; c1 <= 11; c1 += 1) {
    Stmt_for_body3(c0, c1);
    if (c0 == 0 && c1 % 11 == 0)
      Stmt_for_cond1_preheader(c1 / 11);
  }
  Stmt_for_body7_preheader(c0);
  #pragma minimal dependence distance: 1
  for (int c1 = 11; c1 <= 22; c1 += 1) {
    Stmt_for_body7(c0, c1 - 11);
    if (c0 == 1 && c1 % 11 == 0)
      Stmt_for_inc13((c1 / 11) - 1);
  }
}

else
{ /* original code */ }

Stmt_for_body3 is being scheduled before Stmt_for_cond1_preheader. When polly-opt-simplify-deps=yes or when polly-opt-max-coefficient has values less than 11, we get the right schedule.