polly crashes with "opt -mem2reg -polly-mse" while running pass 'Polly - Maximal static expansion of SCoP'

[Quuxplusone]

Bugzilla Link	PR34458
Status	NEW
Importance	P enhancement
Reported by	Zhendong Su (su@cs.ucdavis.edu)
Reported on	2017-09-04 08:30:08 -0700
Last modified on	2017-12-12 01:32:10 -0800
Version	unspecified
Hardware	PC All
CC	ditaliano@apple.com, llvm-bugs@lists.llvm.org, simbuerg@fim.uni-passau.de, tobias@grosser.es
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

$ clangpolly -v
clang version 6.0.0 (http://llvm.org/git/clang.git
9b9a71803226ccc3c9310312967117875b9ff77e) (http://llvm.org/git/llvm.git
2677f9404b42bfb87e26402dc878fe08378c1129)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/su/bin
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/5
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/5.4.0
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/6
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/6.0.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4.7
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.6
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.6.4
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7.4
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8.5
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9.3
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5.4.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6.0.0
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5.4.0
Candidate multilib: .;@m64
Candidate multilib: 32;@m32
Candidate multilib: x32;@mx32
Selected multilib: .;@m64
$
$ clangpolly -O3 -mllvm -disable-llvm-optzns -c -emit-llvm -o small.bc small.c
$ optpolly -mem2reg -polly-mse -o small-opt.bc small.bc
#0 0x00000000039745c5 (optpolly+0x39745c5)
#1 0x0000000003974658 (optpolly+0x3974658)
#2 0x000000000397289f (optpolly+0x397289f)
#3 0x0000000003973e3a (optpolly+0x3973e3a)
#4 0x00007f678c5fa390 __restore_rt (/lib/x86_64-linux-
gnu/libpthread.so.0+0x11390)
#5 0x0000000003c979c4 (optpolly+0x3c979c4)
#6 0x0000000003c9a8a0 (optpolly+0x3c9a8a0)
#7 0x0000000003c9a8d1 (optpolly+0x3c9a8d1)
#8 0x0000000003cc4706 (optpolly+0x3cc4706)
#9 0x0000000003cca87b (optpolly+0x3cca87b)
#10 0x0000000003ccb560 (optpolly+0x3ccb560)
#11 0x0000000003d7a943 (optpolly+0x3d7a943)
#12 0x0000000002acfaf0 (optpolly+0x2acfaf0)
#13 0x00000000031f6f6e (optpolly+0x31f6f6e)
#14 0x00000000031f7107 (optpolly+0x31f7107)
#15 0x00000000031f7482 (optpolly+0x31f7482)
#16 0x00000000031f7b97 (optpolly+0x31f7b97)
#17 0x00000000031f7da3 (optpolly+0x31f7da3)
#18 0x000000000172ca2e (optpolly+0x172ca2e)
#19 0x00007f678b357830 __libc_start_main /build/glibc-bfm8X4/glibc-
2.23/csu/../csu/libc-start.c:325:0
#20 0x0000000001704069 (optpolly+0x1704069)
Stack dump:
0.  Program arguments: optpolly -mem2reg -polly-mse -o small-opt.bc small.bc
1.  Running pass 'Function Pass Manager' on module 'small.bc'.
2.  Running pass 'Region Pass Manager' on function '@foo'
3.  Running pass 'Polly - Maximal static expansion of SCoP' on basic block
'%while.cond'
Segmentation fault (core dumped)
$

--------------------------------

int a, b;

void foo ()
{
  for (; a; a++)
    {
      int c;
      while (c)
    ;
      for (; c < 1; c++)
    b = 1;
    }
}

int main ()
{
  foo ();
  return 0;
}

[Quuxplusone]

Reduced (opt -polly-mse)

@global = external global i32, align 4
@global.1 = external global i32, align 4

define void @patatino() {
bb:
  br label %bb1

bb1:
  %tmp = phi i32 [ undef, %bb ], [ %tmp10, %bb15 ]
  br label %bb5

bb5:
  %tmp6 = icmp ne i32 %tmp, 0
  br i1 %tmp6, label %bb5, label %bb9

bb9:
  %tmp10 = phi i32 [ %tmp14, %bb12 ], [ %tmp, %bb5 ]
  %tmp11 = icmp slt i32 %tmp10, 1
  br i1 %tmp11, label %bb12, label %bb15

bb12:
  store i32 1, i32* @global.1, align 4
  %tmp14 = add nsw i32 %tmp10, 1
  br label %bb9

bb15:
  %tmp17 = load i32, i32* @global, align 4
  br label %bb1
}

[Quuxplusone]

It crashes with the following assertion:

opt: /home/davide/work/llvm-
polly/tools/polly/lib/Transform/MaximalStaticExpansion.cpp:439:
polly::ScopArrayInfo*
{anonymous}::MaximalStaticExpander::expandAccess(polly::Scop&,
polly::MemoryAccess*): Assertion `!UpperBound.is_null() && UpperBound.is_pos()
&& !UpperBound.is_nan() && "The upper bound is not a positive integer."' failed.

I think I'll try to debug this but I'm not superfamiliar with polly so, Tobias,
if you have ideas, please jump in :)

[Quuxplusone]

Hi Davide,

this code was contributed

[Quuxplusone]

This code was contributed by Andreas' student. It seems we find a negative upper bound at a position this is not expected. Andreas any idea what is going on here?

[Quuxplusone]

Need to debug it, but I would have 2 first guesses:
 1) Outermost statement dimension is unbounded. This should cause the
    loop to be rejected from full expansion. If not, we lack a check.
 2) Innermost statement dimension (c-loop) has the dimension's upper bound
    at the value 0. AFAIK the implementation assumes a constant positive
    upper bound.

I try to have a look in the evening.