Static versioning in the polyhedral model
An approach is presented to enhancing the optimization process in a polyhedral compiler by introducing compile-time versioning, i.e., the production of several versions of optimized code under varying assumptions on its run-time parameters. We illustrate this process by enabling versioning in the polyhedral processor placement pass. We propose an efficient code generation method and validate that versioning can be useful in a polyhedral compiler by performing benchmarking on a small set of deep learning layers defined for dynamically-sized tensors.
1. A method for compiling source code, the method comprising performing by a processor the steps of:
receiving and transforming source code comprising one or more run-time-determinable parameters into a base internal representation (IR) of a polyhedral compiler;
creating a plurality of dedicated versions of the base IR, each dedicated version comprising a respective context that represents a distinct respective combination of potential values of the parameters;
generating a respective source code version corresponding to each dedicated version of the base IR; and
deriving a wrapper function for conditionally invoking the respective source code versions.
2. The method of claim 1 , wherein:
the source code comprises a loop nest, and one of the one or more run-time-determinable parameters comprises a bound of a loop in the loop nest or a memory access variable specified in the loop in the loop nest.
3. The method of claim 1 , wherein:
the base IR comprises a generalized dependence graph (GDG); and
creating the plurality of dedicated versions of the base IR comprises creating a tree of GDGs.
4. The method of claim 1 , wherein for a particular dedicated version of the base IR, a corresponding context representing a corresponding combination of the potential values of the parameters comprises a constraint function in terms of the potential values of one or more of the parameters.
5. The method of claim 4 , further comprising linearizing the constraint function via affine approximation.
6. The method of claim 4 , further comprising linearizing the constraint function using an artificial neural network trained for polyhedral smoothing.
7. The method of claim 1 , wherein to conditionally invoke a particular source code version, the wrapper function is configured for evaluating at runtime the combination of potential values of the parameters.
8. The method of claim 7 , wherein:
the combination of potential values of the parameters is represented as a solution to a set of affine functions; and
evaluating at runtime the combination of potential values of the parameters comprises evaluating each affine function in the set at most once.
9. A system for compiling source code, the system comprising:
a first processor; and
a first memory in electrical communication with the first processor, and comprising instructions that, when executed by a processing unit that comprises one or more computing units, wherein one of the one or more computing units comprises the first processor or a second processor, and wherein the processing unit is in electronic communication with a memory module that comprises the first memory or a second memory, program the processing unit to:
receive and transform source code comprising one or more run-time-determinable parameters into a base internal representation (IR) of a polyhedral compiler;
create a plurality of dedicated versions of the base IR, each dedicated version comprising a respective context that represents a distinct respective combination of potential values of the parameters;
generate a respective source code version corresponding to each dedicated version of the base IR; and
derive a wrapper function for conditionally invoking the respective source code versions.
10. The system of claim 9 , wherein:
the source code comprises a loop nest, and one of the one or more run-time-determinable parameters comprises a bound of a loop in the loop nest or a memory access variable specified in the loop in the loop nest.
11. The system of claim 9 , wherein:
the base IR comprises a generalized dependence graph (GDG); and
to create the plurality of dedicated versions of the base IR, the instructions program the processing unit to create a tree of GDGs.
12. The system of claim 9 , wherein for a particular dedicated version of the base IR, a corresponding context representing a corresponding combination of the potential values of the parameters comprises a constraint function in terms of the potential values of one or more of the parameters.
13. The system of claim 12 , wherein the instructions further program the processing unit to:
linearize the constraint function via affine approximation.
14. The system of claim 12 , wherein the instructions further program the processing unit to:
linearize the constraint function using an artificial neural network trained for polyhedral smoothing.
15. The system of claim 9 , wherein to conditionally invoke a particular source code version, the wrapper function is configured for evaluating at runtime the combination of potential values of the parameters.
16. The system of claim 15 , wherein:
the combination of potential values of the parameters is represented as a solution to a set of affine functions; and
evaluating at runtime the combination of potential values of the parameters comprises evaluating each affine function in the set at most once.