LoopSpawning causes incorrect behavior if the loop body makes use of LimitVar

[VictorYing]

I was having some weird issues with compiling and transforming loops in Swarm programs, and as I started narrowing the problem down, I started to suspect the bug was due in part to code I didn't write, but copied from Tapir's LoopSpawning pass. So I decided to see if I could write a Cilk program that miscompiled in a way analogous to the issue I was having. Here's what I've come up with:

+victory@bcn5 /tmp/victory/llvm-tapir-build $ cat cilktest.c
#include <cilk/cilk.h>
#include <stdio.h>

__attribute__((noinline)) void foo(int limit) {
  cilk_for (int i = 1; i <= limit; i++) {
    printf("Limit is %d\n", limit);
  }
}

int main() {
  printf("Starting\n");
  foo(8);
  printf("Finished\n");
}
+victory@bcn5 /tmp/victory/llvm-tapir-build $ bin/clang --version
clang version 5.0.0 (git@github.com:wsmoses/Cilk-Clang.git cb4e7cc1202c13504de32b352091076560be42c6) (https://github.com/wsmoses/Parallel-IR.git 6ce5f2f27b1bc2d92e48420376c2a37d1608f3a1)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /tmp/victory/llvm-tapir-build/bin
+victory@bcn5 /tmp/victory/llvm-tapir-build $ bin/clang -ftapir cilktest.c
+victory@bcn5 /tmp/victory/llvm-tapir-build $ ./a.out
Starting
Limit is 1
Limit is 1
Limit is 2
Limit is 4
Limit is 4
Limit is 6
Limit is 6
Limit is 8
Limit is 8
Finished
+victory@bcn5 /tmp/victory/llvm-tapir-build $

The above program should only print out a limit value of 8 repeatedly, but, as you can see, it is mis-compiled (with no error messages, even with assertions turned on!) and prints out a variety of different numbers. This is using a compiler generated from the current master branch of this repo, without any modifications from me.

I believe the problem is as follows: the loop invariant value "limit" that already exists in the code (as a formal parameter of foo()) happens to coincide exactly with the loop limit, so when LoopSpawning uses SCEVExpander to build LimitVar (https://github.com/wsmoses/Parallel-IR/blob/6ce5f2f27b1bc2d92e48420376c2a37d1608f3a1/lib/Transforms/Tapir/LoopSpawning.cpp#L1059), no code is actually built and LimitVar just points to the existing "limit" value, which the code in the body of the loop also uses. Then when the loop gets outlined to a helper function, both uses of the limit value in the loop (correctly, the loop limit comparison, but also, incorrectly, the use in the body of the loop) are mapped to the limit argument of the helper, which is the end value of the range to be iterated over for each DAC call.

I infer the numbers printed out come from a DAC spawning call tree that looks like:

            (0,8)
           /     \
      (0,4)       (5,8)
      /   \       /   \
   (0,2) (3,4) (5,6) (7,8)
   /   \
(0,1) (2,2)

Hence 1, 4, 6, and 8 each being printed twice, since these are the "end" values of leaf ranges of size two, and 2 being printed once due to one leaf task being assigned just the single iteration with index 2.

[wsmoses]

Nice catch! Yeah that's broken behavior.

[neboat]

Yep, that's a good catch. I think I know what's going wrong. I can take a look on Wednesday, once some more urgent deadlines are taken care of.