DiagnosticInfo and SCEV

Project Infrastructure LLVM Dev List Archives
1

Hello,

I was thinking about printing SCEV into DiagnosticInfo messages, an example would be to print the loop trip count of loops, or the stride of memory accesses.

I ran into two problems:

  • DiagnosticInfo is in Core, SCEV is in Analysis, so it is a little bit weird (I declare the operator<< overload for SCEV* in DiagnosticInfo, but only define it in ScalarEvolution)
  • I would like to print meaningful expressions that does not involve llvm-ir variables.

I think the second problem is hard, how would you suggest to proceed?

2

- I would like to print meaningful expressions that does not involve llvm-ir
variables.

I don't quite understand what you mean by this -- are you saying you
want to print SCEV expressions that have only constants at the leaves?

In any case, some examples will be helpful.

-- Sanjoy

3

Ah, yes, I should have provided an example:

1: for(int i = 0; i < n/2; ++i)
2: for(int j = 0; j < n; ++j)
3: A[2i+nj] += A[2i+1+nj];

Let say, I have a loop interchange pass that decide it is better for spacial locality, to exchange those two loops.
It might print a diagnostic message:

Deciding to perform loop interchange between outer-loop at line 1 and inner-loop at line 2. Accesses on A at line 3 have a stride of 2 along the outer-loop, which is shorter than the stride of %17 along the inner-loop.

The reason why it says 2 and %17 is because that is the textual representation of SCEV representing the stride. Ideally, %17 would be expressed in terms of the original code, here “n”. I could translate the “leaves” into their debug info, but what about {0,+,1}<%loop1> that I would like to spell, as a block: “i”?

4

Ah, yes, I should have provided an example:

1: for(int i = 0; i < n/2; ++i)
2: for(int j = 0; j < n; ++j)
3: A[2i+nj] += A[2i+1+nj];

Let say, I have a loop interchange pass that decide it is better for spacial locality, to exchange those two loops.
It might print a diagnostic message:

Deciding to perform loop interchange between outer-loop at line 1 and inner-loop at line 2. Accesses on A at line 3 have a stride of 2 along the outer-loop, which is shorter than the stride of %17 along the inner-loop.

The reason why it says 2 and %17 is because that is the textual representation of SCEV representing the stride. Ideally, %17 would be expressed in terms of the original code, here “n”. I could translate the “leaves” into their debug info, but what about {0,+,1}<%loop1> that I would like to spell, as a block: "i”?

I think the best we can do here is to point to the corresponding loop (i.e. "{0,+,1}<%loop1>” ==> “iteration number of loop ‘at line 1: for(int i = 0’ i < n/2; ++i)’ ”). In general, we can not map SCEV expressions to some existing variables/constants in the source code, but in some cases we probably can recognize the meaning of a SCEV expression: e.g. iteration number or (maximum/minimum) trip count.

For example, for a bubble-sort loop, looking like this:

1: for (int i = 0; i < n; i++) {
2: for (int j = 0; j < i; j++) {
3: …
4: }
5: }

Some diagnostic might look like this:

Deciding to optimize loop at line 2 iterating up to loop at line 1 iteration number of times.

However, I admit it might look a bit clunky though :confused:

Michael