LLVM Polly to DaCe

[Lukas Trümper]

Hello,

I am working on a project where I lift Scops to SDFGs and then use DaCe to optimize and generate code into a separate source file (~ a library). I want to remove the Scop in the source file and replace it with calls to the library functions.

I have a basic implementation for the lifting to SDFGs and for replacing Scops, but I have many, many questions:

- Lifting: I am exporting via JScop and parsing the JSON to an SDFG in Python using the SDFG API. I am converting domains to SDFG maps and LLVM instructions to Tasklets inside those maps (purely data-centric). To someone who also knows DaCe: Would it make sense to lift the Scop to the SDFG using state transitions and then apply LoopToMap analysis? I am worried that the instructions in the JScop and the domain are insufficient to represent the algorithm.

- Cutout: I am using the terminator of the entering block to redirect the control flow around the Scop to the existing block. The Scop is then automatically removed by dead code elimination. Calls to the SDFG are inserted before the terminator. On polybench, I get errors that the terminator cannot be found. There should always be a terminator inside the entering block, right? Is there a smarter way to do it?

- PyISL: I would like to use PyISL to parse the string into ISL objects rather than writing a new string parser. Is there an example of how to use PyISL with JScop output?

- False Domain: I have seen domains where the JSON contains false. Are those empty domains or invalid domains?

- Strategy: Since a Scop may contain multiple statements, the approach fails if only one cannot be lifted. E.g., a matmul with initialization is two statements;  still, I want to optimize the matmul if the initialization fails to be lifted. Therefore, I would like to replace the code on a statement level rather than a Scop level. Could anyone please give me some input here? It seems possible to only get blocks related to one statement. Are blocks unique, or could they contain multiple statements?

My motivation is to use transfer tuning (and also apply non-polyhedral optimization, e.g., local storage) and so I cannot use the integrated code generator for ISL-based schedules.

Any ideas, comments, and input are very welcome!

Cheers,

Lukas

[Michael Kruse]

I am not familiar with DaCo or SDFGs, but I can help with the Polly part.

Am Fr., 14. Apr. 2023 um 09:27 Uhr schrieb Lukas Trümper <truempe...@gmail.com>:

- Cutout: I am using the terminator of the entering block to redirect the control flow around the Scop to the existing block. The Scop is then automatically removed by dead code elimination. Calls to the SDFG are inserted before the terminator. On polybench, I get errors that the terminator cannot be found. There should always be a terminator inside the entering block, right? Is there a smarter way to do it?

A BB must alway finish with a terminator, or the Verifier will fail because of a degenerate block. You can always add an UnreachableInst with no terminator exists.

 

- PyISL: I would like to use PyISL to parse the string into ISL objects rather than writing a new string parser. Is there an example of how to use PyISL with JScop output?

No JScop is a format internal to Polly used for regression tests. It is not meant as an exchange format.

 

- False Domain: I have seen domains where the JSON contains false. Are those empty domains or invalid domains?

In that case Polly determined that the statement is never executed. That can be because of assumptions Polly made, e.g. a flag called `debug` is always false, hence a BB with a condition `if (debug)` will never execute. If `debug` actually is true, then the fallback (original) code will be executed instead.

- Strategy: Since a Scop may contain multiple statements, the approach fails if only one cannot be lifted. E.g., a matmul with initialization is two statements;  still, I want to optimize the matmul if the initialization fails to be lifted. Therefore, I would like to replace the code on a statement level rather than a Scop level. Could anyone please give me some input here? It seems possible to only get blocks related to one statement. Are blocks unique, or could they contain multiple statements?

Polly can only process what it can represent as a SCoP. By default it may fail if some statement would pessimize the representation too much. However, there are switches in ScopDetection that add ScopStmts that are modeled as all data is read and written.

Michael

--

Tardyzentrismus verboten!

[Lukas Trümper]

Hello Michael,

thanks for the answers!

I have another question: Assume a typical initialization loop of polybench, where an array is assigned the iteration variable, i.e. A[i] = i. When I look at the Scop and the statement of such a loop, it usually contains 1-2 instructions: a "store double %X, ..." and possibly a "%X = sitofp i32 %Y" depending on the types. How can I now trace back where %X comes from, i.e., that it is the iteration variable of the surrounding loop? Would I call getSurroundingLoop method and then check the LoopInfo. So I am wondering about the mapping of loop variables to identifiers in instructions for statements.

I was hoping that Scops already have a mapping of the iteration variables to inputs/parameters of the statement.

Cheers,

Lukas

[Lukas Trümper]

Found the answer already: getLoopForDimension() and then use the PHINode of the induction variable to find the correspondence between dimensions and loop var.

[Lukas Trümper]

Hello,

Another question . A Scop for Cholesky gives the following context and schedule:

And when I parse an AST from it, the context is not converted into an outer loop (see attached ast.json). Is the Scop parametric, and is the "context" outside the Scop? I.e., the Scop is called for each p_0?

Is there a way to generate an AST containing the context?

Cheers,

Lukas

Michael Kruse schrieb am Mittwoch, 19. April 2023 um 22:30:08 UTC+2: