Help Needed: Compatible Barvinok + ISL Versions for Loop Memory Access Volume Estimation

[Avinash M N]

Hi all,

I'm currently working on estimating memory access volume (number of iterations per variable) in loop programs as part of a project.

To compute the number of memory accesses per statement, I am trying to use Barvinok and ISL to extract the iteration count and symbolic cardinality of access relations.

However, it seems that the Barvinok version I installed (version details are specified below) is using the bundled ISL, which might not support full cardinality computation, or at least I’m not able to access symbolic cardinality functions from it.

Could you please suggest:

- The correct version of Barvinok + ISL known to support symbolic volume (cardinality) estimation reliably?

- Any build flags or configuration steps I should ensure while compiling from source?

- If there’s a known minimal test case or script to verify the volume estimation functionality?

Any help or references would be greatly appreciated!

Here is my current setup:

ISCC Version Info:

isl-0.27-GMP

barvinok-0.41.3

clang version 9.0.1

pet-0.11.8

Thanks in advance!

Best regards,

Avinash

[Sven Verdoolaege]

On Tue, Jun 17, 2025 at 02:02:24AM -0700, Avinash M N wrote:
>
>
> Hi all,
>
> I'm currently working on estimating memory access volume (number of
> iterations per variable) in loop programs as part of a project.
>
> To compute the number of memory accesses per statement, I am trying to use
> Barvinok and ISL to extract the iteration count and symbolic cardinality of
> access relations.
>
> However, it seems that the Barvinok version I installed (version details
> are specified below) is using the bundled ISL, which might not support full
> cardinality computation, or at least I’m not able to access symbolic
> cardinality functions from it.

What does this mean?
What exactly are you trying to do and how did it fail?

> - If there’s a known minimal test case or script to verify the volume
> estimation functionality?

make check

> Here is my current setup:
>
> ISCC Version Info:
>
> isl-0.27-GMP
>
> barvinok-0.41.3
>
> clang version 9.0.1
>
> pet-0.11.8

I'm surprised barvinok-0.41.3 compiles with isl-0.27.
Why aren't you using the latest version (barvinok-0.41.8)?

skimo

[Avinash M N]

Dear Mr. Verdoolaege,

Thank you for your response.

I am planning to use Barvinok for counting loop iterations from affine/nested loop programs by representing their iteration domains as parametric polytopes.

I went through the README and setup instructions, but could not find the specific versions of the required dependencies (ISL, NTL, LLVM/Clang, GMP, etc.) that are known to work reliably with the current version of Barvinok.

Could you kindly let me know which versions of these dependencies are recommended for a successful build and usage?

Thank you for your time and support.

Best regards,
Avinash M N

[Sven Verdoolaege]

On Sun, Jun 22, 2025 at 09:23:01AM -0700, Avinash M N wrote:
> I went through the README and setup instructions, but could not find the
> specific versions of the required dependencies (ISL, NTL, LLVM/Clang, GMP,
> etc.) that are known to work reliably with the current version of Barvinok.

The bundled version of isl should obviously work.
I'm not aware of any compatibility issues with any reasonably recent
version of NTL or GMP.
For LLVM/Clang, see pet/README.

skimo

[Avinash M N]

Dear Mr. Verdoolaege,

I’m working on developing a compiler for an AI Accelerator, and I have encountered an issue related to cardinality calculation using Barvinok.

As part of the process, I need to convert iteration domains into tiled domains. The iteration domains I am dealing with are represented by ISL constraints, such as:

"[M, T] -> { [i] : 0 <= (i*T) < M }"

However, when there is a multiplication between parameters, such as i×T in the above expression, Barvinok fails to compute the cardinality, with the error message: "expecting constant value, got ident 'T'". This issue arises because the current formulation of the set involves a multiplication between parameters, and I cannot assign a value to T as it must remain symbolic in this context. This seems to be unsupported by Barvinok for cardinality calculations.

Is there a supported method or workaround in Barvinok to handle or approximate such sets, where the constraints involve multiplication between parameters?

I appreciate any advice or suggestions you may have on this type of issue!

Best regards,
Avinash

[Sven Verdoolaege]

On Wed, Jul 09, 2025 at 06:24:04AM -0700, Avinash M N wrote:
> Dear Mr. Verdoolaege,
>
> I’m working on developing a compiler for an AI Accelerator, and I have
> encountered an issue related to cardinality calculation using Barvinok.
>
> As part of the process, I need to convert iteration domains into tiled
> domains. The iteration domains I am dealing with are represented by ISL
> constraints, such as:
> "[M, T] -> { [i] : 0 <= (i*T) < M }"

These are not isl constraints. isl only deals with sets defined
by affine constraints and as you have figured out already,
these are not affine constraints.

> However, when there is a multiplication between parameters, such as i×T in
> the above expression, Barvinok fails to compute the cardinality, with the

> error message: *"expecting constant value, got ident 'T'"*. This issue

> arises because the current formulation of the set involves a multiplication

> between parameters, and *I cannot assign a value to T *as it must remain

"i" is not a parameter, but a multiplication of a variable and a parameter
is also not allowed.

> Is there a supported method or workaround in Barvinok to handle or
> approximate such sets, where the constraints involve multiplication between
> parameters?

If you want an approximation, you can plug in the smallest and largest
possible value of T.

If it's only constraints of this form, you can introduce a parameter
M_div_T representing M//T, compute the cardinality of

[M_div_T] -> { [i] : 0 <= i < M_div_T }

and then plug in M//T for M_div_T in the result.

skimo